Peer-Reviewed Journal Details
Mandatory Fields
Chen, Jianer and Liu, Yang and Lu, Songjian and O'Sullivan, Barry and Razgon, Igor
2008
November
Journal of The ACM
A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem
Published
Optional Fields
55
5
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!nO(1) for the DFVS problem. Therefore, we resolve this open problem.
10.1145/1411509.1411511
Grant Details