The parameterized complexity of the induced matching problem
The parameterized complexity of the induced matching problem
复制标题
DOI：
10.1016/j.dam.2008.07.011
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
Hannes Moser;S. Sikdar
中科院分区：
文献类型：
--
作者：
Hannes Moser;S. Sikdar
给定一个图G和一个整数k≥0，NP-完全诱导匹配问题问是否存在一个大小至少为k的边子集M，使得M是一个匹配，并且M的两条边都不被G的一条边连接。这个问题的复杂性，一般的图，以及对许多限制图类已被深入研究。然而，除了这个问题在一般图上是W[1]-困难的事实之外，很少有人知道这个问题在受限图类中的参数化复杂性。在这项工作中，我们提供了第一时间固定参数的易处理性结果平面图，有界度图，图周长至少为6，二分图，线图，有界树宽的图形。特别地，我们给出了平面图的线性尺寸问题核。
Given a graph G and an integer k≥0, 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.