Edge deletion to tree-like graph classes
share
For a fixed property (graph class) Π, given a graph G and an integer k, the Π-deletion problem consists in deciding if we can turn G into a graph with the property Π by deleting at most k edges of G. The Π-deletion problem is known to be NP-hard for most of the well-studied graph classes (such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others), with the notable exception of trees. Motivated by this fact, in this work we study the deletion problem for some classes close to trees. We obtain NP-hardness results for several classes of sparse graphs, for which we prove that deletion is hard even when the input is a bipartite graph. In addition, we give sufficient structural conditions for the graph class Π for NP-hardness. In the case of deletion to cactus, we show that the problem becomes tractable when the input is chordal, and we give polynomial-time algorithms for quasi-threshold graphs.
READ FULL TEXT