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

Abstract

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph G and a parameter k , either construct a feedback vertex set of at most k vertices in G or report that no such a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time f ( k ) n O (1) for some function f . In this article, we develop new algorithmic techniques that result in an algorithm with running time 4 k k ! n O (1) for the DFVS problem. Therefore, we resolve this open problem.