Hardness of edge-modification problems

• Published in: Theoretical computer science 2009-11, Vol.410 (47), p.4920-4927
• Main Authors: Alon, Noga, Stav, Uri
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Approximations and expansions; Computer science; control theory; systems; Edge modification problems; Edit distance; Exact sciences and technology; Hardness of approximation; Hereditary graph properties; Information retrieval. Graph; Mathematical analysis; Mathematics; Miscellaneous; Sciences and techniques of general use; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2009.07.002

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 ( n 2 ) 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 ( n 2 − ε ) additive approximation is N P -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 ( n 2 ) 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 N P -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 .