Contracting few edges to remove forbidden induced subgraphs
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractFor 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, {Cl : 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 Cl for some l ≥ 4 or a fixed path Pl for some odd l ≥ 5. © 2013 Springer International Publishing.
All Author(s) ListCai L., Guo C.
Name of Conference8th International Symposium on Parameterized and Exact Computation, IPEC 2013
Start Date of Conference04/09/2013
End Date of Conference06/09/2013
Place of ConferenceSophia Antipolis
Country/Region of ConferenceFrance
Detailed descriptioned. by Gregory Gutin & Stefan Szeider.
Volume Number8246 LNCS
PublisherSpringer Verlag
Place of PublicationGermany
Pages97 - 109
LanguagesEnglish-United Kingdom

Last updated on 2020-25-10 at 01:14