Additive approximation for edge-deletion problems
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)
Abstract: A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E_P(G). Our first result states that for any monotone graph property P, any epsilon >0 and n-vertex input graph G one can approximate E_P(G) up to an additive error of epsilon n^2 Our second main result shows that such approximation is essentially best possible and for most properties, it is NP-hard to approximate E_P(G) up to an additive error of n^{2-delta}, for any fixed positive delta. The proof requires several new combinatorial ideas and involves tools from Extremal Graph Theory together with spectral techniques. Interestingly, prior to this work it was not even known that computing E_P(G) precisely for dense monotone properties is NP-hard. We thus answer (in a strong form) a question of Yannakakis raised in 1981.
Recommendations
Cites work
- scientific article; zbMATH DE number 1696630 (Why is no real title available?)
- scientific article; zbMATH DE number 1819631 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1241385 (Why is no real title available?)
- scientific article; zbMATH DE number 1857651 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- A separation theorem in property testing
- An Application of Duality to Edge-Deletion Problems
- An Optimal Algorithm for Checking Regularity
- Complexity classification of some edge modification problems
- Density conditions for triangles in multipartite graphs
- Edge-Deletion Problems
- Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
- Efficient testing of large graphs
- Every Monotone Graph Property Is Testable
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Integer and fractional packing of families of graphs
- Integer and fractional packings in dense graphs
- MAX-CUT has a randomized approximation scheme in dense graphs
- On a problem of K. Zarankiewicz
- On a valence problem in extremal graph theory
- On extremal problems of graphs and generalized graphs
- On the complexity of DNA physical mapping
- On the connection between chromatic number, maximal clique and minimal degree of a graph
- On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Pseudo-random graphs
- Quick approximation to matrices and applications
- Random sampling and approximation of MAX-CSP problems
- Ranking Tournaments
- Testing versus estimation of graph properties
- The Algorithmic Aspects of the Regularity Lemma
- The complexity of some edge deletion problems
- The node-deletion problem for hereditary properties is NP-complete
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Tolerant property testing and distance approximation
Cited in
(24)- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
- Finding small stabilizers for unstable graphs
- Dilation-Optimal Edge Deletion in Polygonal Cycles
- Hardness of edge-modification problems
- Additive approximation of generalized Turán questions
- Estimating parameters associated with monotone properties
- Many disjoint triangles in co-triangle-free graphs
- Parameterized complexity of Eulerian deletion problems
- Strategyproof mechanisms for \(2\)-facility location games with minimax envy
- Strategyproof mechanisms for 2-facility location games with minimax envy
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- EDGE-DELETION GRAPH PROBLEMS WITH FIRST-ORDER EXPRESSIBLE SUBGRAPH PROPERTIES
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Local-vs-global combinatorics
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Complexity of near-3-choosability problem
- Hardness of fully dense problems
- Extremal results in sparse pseudorandom graphs
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Trimming forests is hard (unless they are made of stars)
- Edit distance measure for graphs.
- Graph stabilization: a survey
- Efficient stabilization of cooperative matching games
This page was built for publication: Additive approximation for edge-deletion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389218)
