Hermelin, DannyDannyHermelinMnich, MatthiasMatthiasMnichLeeuwen, Erik Jan vanErik Jan vanLeeuwen2020-01-242020-01-242012European Symposium on Algorithms (ESA 2012)http://hdl.handle.net/11420/4584The 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.enInformatikConference Paper10.1007/978-3-642-33090-2_54Other