Counting Matchings of Size k Is W[1]-Hard
Counting Matchings of Size k Is W[1]-Hard
复制标题
DOI：
10.1007/978-3-642-39206-1_30
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Radu Curticapean
中科院分区：
文献类型：
--
作者：
Radu Curticapean
我们证明了以下参数化计数问题的[1]-硬度：给定一个简单的无向图g和一个参数k∈n，计算sizekinG的匹配个数。从[1]中我们知道，给定一个边加权图g，很难在匹配inGisW[1]上计算一个特定的加权和。在本文中，我们展示了一个不需要权重的缩减。这解决了[5]中的一个开放问题，并在[5]的稀缺问题列表中增加了一个自然参数化计数问题。由于这个问题的经典版本得到了很好的研究，我们相信我们的结果有助于未来对其他问题的w[1]-硬度证明。
We proveW[1]-hardness of the following parameterized counting problem: Given a simple undirected graphGand a parameterk∈ ℕ, compute the number of matchings of sizekinG.It is known from [1] that, given an edge-weighted graphG, computing a particular weighted sum over the matchings inGisW[1]-hard. In the present paper, we exhibit a reduction that does not require weights.This solves an open problem from [5] and adds a natural parameterized counting problem to the scarce list ofW[1]-hard problems. Since the classical version of this problem is well-studied, we believe that our result facilitates futureW[1]-hardness proofs for other problems.