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.