An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertez Set Problem
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(ckn3) 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 2O(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 annotated form of the problem, where a subset of the vertices may be marked as not 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(2o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT=M1.
Frank Dehne Michael Fellows Michael A. Langston Frances Rosamond Kim Stevens
Carleton University, Ottawa, Canada University of Newcastle, Callaghan NSW 2308, Australia University of Tennessee, Knoxville TN 37996-3450, USA The Mechanics Institute, Bobs Farm NSW 2316, Australia
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
859-869
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）