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

共 23 条

[1]

[Anonymous], 1992, C NUMERANTIUM

[2] Randomized algorithms for the loop cutset problem [J].

Becker, A ;

Bar-Yehuda, R ;

Geiger, D .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 12 :219-234

[3]

Bodlaender H. L., 1994, International Journal of Foundations of Computer Science, V5, P59, DOI 10.1142/S0129054194000049

[4]

Bodlaender HL, 2008, LECT NOTES COMPUT SC, V5018, P160, DOI 10.1007/978-3-540-79723-4_16

[5]

Bodlaender HL, 2007, LECT NOTES COMPUT SC, V4393, P320

[6]

BODLAENDER HL, 2006, P INT WORKSH PAR EX

[7]

Burrage K, 2006, LECT NOTES COMPUT SC, V4169, P192

[8]

Chen J, 2008, ACM S THEORY COMPUT, P177

[9]

Dehne F, 2005, LECT NOTES COMPUT SC, V3595, P859, DOI 10.1007/11533719_87

[10]

Downey R. G., 1999, MG COMP SCI

← 1 2 3 →