A 4k2 Kernel for Feedback Vertex Set

被引：110

作者：

Thomasse, Stephan ^{[1
]}

机构：

[1] LIRMM, F-34392 Montpellier, France

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2010年 / 6卷 / 02期

关键词：

Algorithms; Kernelization; feedback vertex set; matching; fixed parameter tractability; ALGORITHMS; PATHS;

D O I：

10.1145/1721837.1721848

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 4k(2) 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(k(11)) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.

引用

页数：8