On Feedback Vertex Set Problems

A feedback vertex set (fvs) in a graph G is a set of vertices F such that G-F is acyclic. The Feedback Vertex Set problem is: given a graph G and a positive integer k, decide if G has a fvs of size at most k. This problem was among the first problems that were shown to be NP-hard, and has received considerable attention from both the approximability and the parameterized complexity points of view.

I will talk about a recent result by Guo et al. showing that the problem admits parameterized algorithms of running time 2^{O(k)} poly(n). This result was also obtained independently by Dehne et al. I will also survey some open problems about feedback vertex sets.