TY - JOUR

T1 - Hardness of edge-modification problems

AU - Alon, Noga

AU - Stav, Uri

N1 - Funding Information:
First author’s research supported in part by the Israel Science Foundation, by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University and by the Von Neumann Fund.

PY - 2009/11/6

Y1 - 2009/11/6

N2 - For a graph property P consider the following computational problem. Given an input graph G, what is the minimum number of edge modifications (additions and/or deletions) that one has to apply to G in order to turn it into a graph that satisfies P? Namely, what is the edit distance Δ (G,P) of a graph G from satisfying P? Clearly, the computational complexity of such a problem strongly depends on P. For over 30 years this family of computational problems has been studied in several contexts and various algorithms, as well as hardness results, were obtained for specific graph properties. Alon, Shapira and Sudakov studied in [N. Alon, A. Shapira, B. Sudakov, Additive approximation for edge-deletion problems, in: Proc. of the 46th IEEE FOCS, 2005, 419-428. Also: Annals of Mathematics (in press)] the approximability of the computational problem for the family of monotone graph properties, namely properties that are closed under removal of edges and vertices. They describe an efficient algorithm that achieves an o(n2) additive approximation to Δ G,P) for any monotone property P, where G is an n-vertex input graph, and show that the problem of achieving an O(n2-ε) additive approximation is NP-hard for most monotone properties. The methods in [N. Alon, A. Shapira, B. Sudakov, Additive approximation for edge-deletion problems, in: Proc. of the 46th IEEE FOCS, 2005, 419-428. Also: Annals of Mathematics (in press)] also provide a polynomial time approximation algorithm which computes Δ(G,P) ± o(n2) for the broader family of hereditary graph properties (which are closed under removal of vertices). In this work we introduce two approaches for showing that improving upon the additive approximation achieved by this algorithm is NP-hard for several sub-families of hereditary properties. In addition, we state a conjecture on the hardness of computing the edit distance from being induced H-free for any forbidden graph H.

AB - For a graph property P consider the following computational problem. Given an input graph G, what is the minimum number of edge modifications (additions and/or deletions) that one has to apply to G in order to turn it into a graph that satisfies P? Namely, what is the edit distance Δ (G,P) of a graph G from satisfying P? Clearly, the computational complexity of such a problem strongly depends on P. For over 30 years this family of computational problems has been studied in several contexts and various algorithms, as well as hardness results, were obtained for specific graph properties. Alon, Shapira and Sudakov studied in [N. Alon, A. Shapira, B. Sudakov, Additive approximation for edge-deletion problems, in: Proc. of the 46th IEEE FOCS, 2005, 419-428. Also: Annals of Mathematics (in press)] the approximability of the computational problem for the family of monotone graph properties, namely properties that are closed under removal of edges and vertices. They describe an efficient algorithm that achieves an o(n2) additive approximation to Δ G,P) for any monotone property P, where G is an n-vertex input graph, and show that the problem of achieving an O(n2-ε) additive approximation is NP-hard for most monotone properties. The methods in [N. Alon, A. Shapira, B. Sudakov, Additive approximation for edge-deletion problems, in: Proc. of the 46th IEEE FOCS, 2005, 419-428. Also: Annals of Mathematics (in press)] also provide a polynomial time approximation algorithm which computes Δ(G,P) ± o(n2) for the broader family of hereditary graph properties (which are closed under removal of vertices). In this work we introduce two approaches for showing that improving upon the additive approximation achieved by this algorithm is NP-hard for several sub-families of hereditary properties. In addition, we state a conjecture on the hardness of computing the edit distance from being induced H-free for any forbidden graph H.

KW - Edge modification problems

KW - Edit distance

KW - Hardness of approximation

KW - Hereditary graph properties

UR - http://www.scopus.com/inward/record.url?scp=84858709501&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858709501&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.07.002

DO - 10.1016/j.tcs.2009.07.002

M3 - Article

AN - SCOPUS:84858709501

VL - 410

SP - 4920

EP - 4927

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 47-49

ER -