2008/10/01 by Jianer Chen, Yang Liu, Songjian Lu +2 · 297 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #semigroups and automata theory #Parameterized complexity #Feedback vertex set #Vertex (graph theory) #Feedback arc set #Vertex cover #Mathematics #Combinatorics #Set (abstract data type) #Directed graph #Computation #Algorithm #Graph #Discrete mathematics #Computer science #Line graph
paper · doi:10.1145/1411509.1411511
published in Journal of the ACM 55(5), 1-19 (Association for Computing Machinery)
openalex publication_date 2008/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
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.