Complexity classification of some edge modification problems (Q4944968)

In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy, a certain property. The authors prove in this paper the NP-hardness of a variety of edge modification problems with respect to some well-studied classes of graphs such as perfect, chordal, chain, comparability, split and asteroidal triple free graphs. Moreover, some of these problems become polynomially solvable when the input graph has bounded degree. The authors give a general constant factor approximation algorithm for deletion and editing problems on bounded degree graphs w.r.t. properties that can be characterized by a finite set of forbidden induced subgraphs. The modification problems are motivated by applications in physical mapping of DNA. For the entire collection see [Zbl 0929.00074].