Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set

Abstract

We give a O(maxû12^k, (4lgk)^ký·n^ω) algorithm for testing whether an undirected graph on n vertices has a feedback vertex set of size at most k where O(nω) is the complexity of the best matrix multiplication algorithm. The previous best fixed parameter tractable algorithm for the problem took O((2k+1)^kn²) time. The main technical lemma we prove and use to develop our algorithm is that that there exists a constant c such that, if an undirected graph on n vertices with minimum degree 3 has a feedback vertex set of size at most c√n, then the graph will have a cycle of length at most 12. This lemma may be of independent interest. We also show that the feedback vertex set problem can be solved in O(d^kkn) for some constant d in regular graphs, almost regular graphs and (fixed) bounded degree graphs.