Complexity classication of some edge modication problems
Assaf Natanzon, Ron Shamir, Roded Sharan · 1999
In an edge modication problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove the NP-hardness of a variety of edge modication problems with respect to some well-studied classes of graphs. These include per- fect, chordal, chain, comparability, split and asteroidal triple free. We show that some of these problems become polynomial when the input graph has bounded degree. We also give a general constant factor approximation algorithm for deletion and editing problems on bounded degree graphs with respect to properties that can be characterized by anite set of forbidden induced subgraphs. ? 2001 Elsevier Science B.V. All rights reserved.