An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem

被引:46
作者
Dehne, Frank [1 ]
Fellows, Michael
Langston, Michael
Rosamond, Frances
Stevens, Kim
机构
[1] Carleton Univ, Ottawa, ON K1S 5B6, Canada
[2] Univ Newcastle, Newcastle, NSW 2308, Australia
[3] Univ Tennessee, Knoxville, TN 37996 USA
关键词
D O I
10.1007/s00224-007-1345-z
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We describe an algorithm for the FEEDBACK VERTEX SET problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c(k) n(3)) where c = 10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2(O(k log k/log log k)). Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish "exponential optimality" for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2(o (k))) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT = M [1].
引用
收藏
页码:479 / 492
页数:14
相关论文
共 31 条
[1]  
ABUKHZAM FN, 2004, ACM SIAM P APPL MATH, V115, P62
[2]   Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs [J].
Alber, J ;
Bodlaender, HL ;
Fernau, H ;
Kloks, T ;
Niedermeier, R .
ALGORITHMICA, 2002, 33 (04) :461-493
[3]  
[Anonymous], 1992, C NUMERANTIUM
[4]   A 2-approximation algorithm for the undirected feedback vertex set problem [J].
Bafna, V ;
Berman, P ;
Fujito, T .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297
[5]   Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference [J].
Bar-Yehuda, R ;
Geiger, D ;
Naor, J ;
Roth, RM .
SIAM JOURNAL ON COMPUTING, 1998, 27 (04) :942-959
[6]   Randomized algorithms for the loop cutset problem [J].
Becker, A ;
Bar-Yehuda, R ;
Geiger, D .
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 12 :219-234
[7]  
Bodlaender H. L., 1994, International Journal of Foundations of Computer Science, V5, P59, DOI 10.1142/S0129054194000049
[8]   On the existence of subexponential parameterized algorithms [J].
Cai, LM ;
Juedes, D .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) :789-807
[9]  
Chen JN, 2005, LECT NOTES COMPUT SC, V3404, P269
[10]   On miniaturized problems in parameterized complexity theory [J].
Chen, YJ ;
Flum, J .
PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 2004, 3162 :108-120