Options
Parameterized complexity of induced H-matching on claw-free graphs
Publikationstyp
Conference Paper
Date Issued
2012
Sprache
English
TORE-URI
Start Page
624
End Page
635
Citation
European Symposium on Algorithms (ESA 2012)
Contribution to Conference
Publisher DOI
Publisher
Springer Nature
The Induced H -Matching problem asks to find k disjoint, induced subgraphs isomorphic to H in a given graph G such that there are no edges between vertices of different subgraphs. This problem generalizes amongst others the classical Independent Set and Induced Matching problems. We show that Induced H -Matching is fixed-parameter tractable in k on claw-free graphs when H is a fixed connected graph of constant size, and even admits a polynomial kernel when H is a clique. Both results rely on a new, strong algorithmic structure theorem for claw-free graphs. To show the fixed-parameter tractability of the problem, we additionally apply the color-coding technique in a nontrivial way. Complementing the above two positive results, we prove the W[1]-hardness of Induced H -Matching for graphs excluding K 1,4 as an induced subgraph. In particular, we show that Independent Set is W[1]-hard on K 1,4-free graphs.
DDC Class
004: Informatik