Additive approximation for edge-deletion problems

Noga Alon, Asaf Shapira, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

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). The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property. For any ε> 0 and any monotone property P, there is a deterministic algorithm, which given a graph G of size n, approximates E′ P(G) in time O(n 2) to within an additive error of εn 2. Given the above, a natural question is for which monotone properties one can obtain better additive approximations of E′ P. Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist. 1. If there is a bipartite graph that does not satisfy P, then there is a δ > O for which it is possible to approximate E′ P to within an additive error of n 2-δ in polynomial time. 2. On the other hand, if all bipartite graphs satisfy P, then for any δ > 0 it is N P-hard to approximate E′ P to within an additive error of n 2-δ. While the proof of (1) is simple, the proof of (2) requires several new ideas and involves tools from Extremal Graph Theory together with spectral techniques. This approach may be useful for obtaining other hardness of approximation results. Interestingly, prior to this work it was not even known that computing E′ P precisely for the properties in (2) is N P-hard. We thus answer (in a strong form) a question of Yannakakis [38], who asked in 1981 if it is possible to find a large and natural family of graph properties for which computing E′ P is N P-hard.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages419-428
Number of pages10
DOIs
StatePublished - 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Additive approximation for edge-deletion problems'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Shapira, A., & Sudakov, B. (2005). Additive approximation for edge-deletion problems. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 (pp. 419-428). [1530734] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.11