Faster fixed parameter tractable algorithms for finding feedback vertex sets

Abstract

A feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n^1−ϵ vertices, then there is a cycle of length at most 6/ϵ (for ϵ ≥ 1/2, we can even improve this to just 6).Using this, we obtain a O((12 log k/log log k+6)^k nω algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k. Here nω is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took O((2k+1)^kn²) time.We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.