A Quartic Kernel for Pathwidth-One Vertex Deletion
A Quartic Kernel for Pathwidth-One Vertex Deletion
复制标题
用于路径宽度一个顶点删除的四次核
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Yngve Villanger
中科院分区：
文献类型：
--
作者：
Geevarghese Philip;Venkatesh Raman;Yngve Villanger
图的路径宽度是图与路径相似程度的度量。给定一个图G和一个整数k，求G中是否存在最多k个顶点，这些顶点的删除会导致一个路径宽度最多为1的图，这个问题是np完全的。我们开始研究这个问题的参数化复杂性，用k来参数化。我们证明了这个问题有一个四次顶点核：我们证明，给定一个输入实例（G = (V， E), k）；|V| = n，我们可以在多项式时间内构造一个实例（G ', k ‘），使得(i) （G, k）是一个YES实例当且仅当（G ’， k ‘）是一个YES实例，（ii） G ’有O（k4）个顶点，（iii） k '≤k。我们还给出了一个固定参数可处理（FPT）算法，该算法在O（7kk * n2）时间内运行。
The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP-complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k); |V| = n, we can construct, in polynomial time, an instance (G′, k′) such that (i) (G, k) is a YES instance if and only if (G′, k′) is a YES instance, (ii) G′ has O(k4) vertices, and (iii) k′ ≤ k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O(7kk ċ n2) time.