Output details

A fixed-parameter algorithm for the directed feedback vertex set problem

<12> We establish fixed-parameter tractability of the Directed Feedback Vertex Set problem, thus resolving arguably the most famous open question in the area of parameterized algorithms. It stayed open since the mid 1980s despite numerous attempts by many researchers. In the book "Invitation to fixed-parameter algorithms", Rolf Niedermeier puts this question as number 1 in the list of central challenges in parameterized algorithmics. This paper resulted in much follow up work by others, including several generalizations, applications to computational biology and to the theory and social choice, and an efficient implementation. This paper is an extended version of a paper presented at the STOC 2008 conference.