Parameterized complexity of induced H-matching on claw-free graphs

DOI10.1007/978-3-642-33090-2_54MaRDI QIDQ2912880zbMATH OpenOpenAlexFDO

Authors Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.7105

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: 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 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 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 NP-complete, depending on the connectivity of H and the structure of G.

Recommendations

• Parameterized complexity of induced graph matching on claw-free graphs
• The parameterized complexity of the induced matching problem
• Induced disjoint paths in claw-free graphs
• Induced disjoint paths in claw-free graphs
• Parameterized complexity of independent set in \(H\)-free graphs

Cited in

(7)

• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Improved FPT algorithms for weighted independent set in bull-free graphs
• Parameterized complexity of independent set in \(H\)-free graphs
• Parameterized complexity of independent set in H-free graphs
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Parameterized complexity of induced graph matching on claw-free graphs
• A connection between sports and matroids: how many teams can we beat?

This page was built for publication: Parameterized complexity of induced \(H\)-matching on claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912880)