Options
Parameterized complexity of induced graph matching on claw-free graphs
Publikationstyp
Journal Article
Date Issued
2014-03-30
Sprache
English
TORE-URI
Journal
Volume
70
Start Page
513
End Page
560
Citation
Algorithmica (2014)
Publisher DOI
ArXiv ID
Publisher
Springer Nature
The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\)-hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\). In particular, we show that Independent Set is \(\mathsf {W}[1]\)-hard on \(K_{1,4}\)-free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\)-complete, depending on the connectivity of \(H\) and the structure of \(G\).
DDC Class
004: Informatik