Additive approximation for edge-deletion problems

DOI10.4007/annals.2009.170.371zbMath1185.05132arXiv0707.0134OpenAlexW2111224696WikidataQ105584518 ScholiaQ105584518MaRDI QIDQ2389218

Noga Alon, Asaf Shapira, Benjamin Sudakov

Publication date: 15 July 2009

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0707.0134

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Additive approximation of generalized Turán questions, Hardness of fully dense problems, Edit distance measure for graphs, Strategyproof mechanisms for \(2\)-facility location games with minimax envy, On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}, Finding small stabilizers for unstable graphs, Local-vs-global combinatorics, Extremal results in sparse pseudorandom graphs, \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, Efficient stabilization of cooperative matching games, Graph Stabilization: A Survey, Strategyproof mechanisms for 2-facility location games with minimax envy, Parameterized Complexity of Eulerian Deletion Problems, Hardness of edge-modification problems, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, Estimating parameters associated with monotone properties, Many disjoint triangles in co-triangle-free graphs, Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid, Editing to a graph of given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Density conditions for triangles in multipartite graphs
• On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
• Integer and fractional packings in dense graphs
• A separation theorem in property testing
• Quick approximation to matrices and applications
• The node-deletion problem for hereditary properties is NP-complete
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• On the complexity of DNA physical mapping
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On extremal problems of graphs and generalized graphs
• Tolerant property testing and distance approximation
• On a valence problem in extremal graph theory
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Random sampling and approximation of MAX-CSP problems
• Testing versus estimation of graph properties
• Every Monotone Graph Property Is Testable
• An Application of Duality to Edge-Deletion Problems
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• The Algorithmic Aspects of the Regularity Lemma
• An Optimal Algorithm for Checking Regularity
• Integer and fractional packing of families of graphs
• MAX-CUT has a randomized approximation scheme in dense graphs
• Ranking Tournaments
• On a problem of K. Zarankiewicz
• Efficient testing of large graphs
• Complexity classification of some edge modification problems