Minimum Feedback Vertex Set for graphs of restricted degree

Abstract

Finding a minimum feedback vertex set, a set whose removal makes a graph acyclic, is an NP-complete problem. We study the behaviour of existing algorithms for this problem on bounded degree graphs. Using the notion of generalized degree, we show that the algorithm of Fomin et al. [2] runs in time O∗ (1.6181n) on graphs of maximum degree three (al- though this case is polynomial-time solvable using a different algorithm) and in contrast, show that for graphs of degree four the generalized de- gree can become arbitrarily large. We show that the algorithm of Xiao [7] runs in time O∗ (1.7180n) on degree four graphs, which improves the best known bound for this case. Finally, we show that we cannot extend the measure of Fomin et al. [2] by using the generalized degree.