We give a O(max{12~k, (4lg k)~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~2) 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 cn~(1/2), 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.
展开▼
