On Parameterized Path and Chordless Path Problems
On Parameterized Path and Chordless Path Problems
复制标题
DOI：
10.1109/ccc.2007.21
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Yijia Chen;J. Flum
中科院分区：
文献类型：
--
作者：
Yijia Chen;J. Flum
我们研究各种路径（和循环）问题的参数化复杂性，参数是路径的长度。例如，我们证明图 G 中长度为 k 的最大路径的存在性问题是固定参数可处理的，而其计数版本是 #W[1]- 完全的。无弦（或诱导）路径的相应问题分别是 W[2]-完全和#W[2]-完全。利用本文开发的工具，我们推导了相关经典问题的 NP 完备性，从而解决了 Hedetniemi 提出的问题。
We study the parameterized complexity of various path (and cycle) problems, the parameter being the length of the path. For example, we show that the problem of the existence of a maximal path of length k in a graph G is fixed-parameter tractable, while its counting version is #W[1]- complete. The corresponding problems for chordless (or induced) paths are W[2]-complete and #W[2]-complete respectively. With the tools developed in this paper we derive the NP-completeness of a related classical problem, thereby solving a problem due to Hedetniemi.