For a given graph property Π (i.e., a collection Π of graphs), the Π-Contraction problem is to determine whether the input graph G can be transformed into a graph satisfying property Π by contracting at most k edges, where k is a parameter. In this paper, we mainly focus on the parameterized complexity of Π-Contraction problems for Π being H-free (i.e., containing no induced subgraph isomorphic to H) for various fixed graphs H. We show that Clique Contraction (equivalently, P3-Free Contraction for connected graphs) is FPT (fixed-parameter tractable) but admits no polynomial kernel unless NP ? coNP/poly, and prove that Chordal Contraction (equivalently, {C_l : l ≥ 4}-Free Contraction) is W[2]-hard. We completely characterize the parameterized complexity of H-Free Contraction for all fixed 3-connected graphs H: FPT but no polynomial kernel unless NP ? coNP/poly if H is a complete graph, and W[2]-hard otherwise. We also show that H-Free Contraction is W[2]-hard whenever H is a fixed cycle C_l for some l ≥ 4 or a fixed path P_l for some odd l ≥ 5.
展开▼
