Directed Feedback Vertex Set is Fixed-Parameter Tractable

Abstract

We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in $O(8^{k}k!\ast poly(n))$.

14 pages