Elsevier

Discrete Applied Mathematics

Volume 157, Issue 4, 28 February 2009, Pages 715-727
Discrete Applied Mathematics

The parameterized complexity of the induced matching problem,☆☆

https://doi.org/10.1016/j.dam.2008.07.011Get rights and content
Under an Elsevier user license
open archive

Abstract

Given a graph G and an integer k0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.

Keywords

Induced matching
Parameterized complexity
Planar graph
Kernelization
Tree decomposition

Cited by (0)

Supported by a DAAD-DST exchange program, D/ 05/57666.

☆☆

An extended abstract of this work appears under the title “The Parameterized Complexity of the Induced Matching Problem in Planar Graphs” in the proceedings of the 2007 International Frontiers of Algorithmics Workshop (FAW’07), Springer, LNCS 4613, pages 325–336, held in Lanzhou, China, August 01–03, 2007.