A 4k2 kernel for feedback vertex set
A 4k2 kernel for feedback vertex set
复制标题
DOI：
10.1145/1721837.1721848
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Stéphan Thomassé
中科院分区：
文献类型：
--
作者：
Stéphan Thomassé
证明了给定一个n阶无向图G和一个整数k，可以在n的多项式时间内计算一个顶点数至多为4k2且k′为整数的图G′，使得G有一个大小至多为k的反馈点集当且仅当G′有一个大小至多为k′的反馈点集.这个结果改进了Burrage等人以前的O（k11）内核，和最近的三次Bodlaender核。这个问题是研究员们提出来的。
We prove that given an undirected graph G on n vertices and an integer k, one can compute, in polynomial time in n, a graph G′ with at most 4k2 vertices and an integer k′ such that G has a feedback vertex set of size at most k iff G′ has a feedback vertex set of size at most k′. This result improves a previous O(k11) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.