TY - GEN
T1 - A fixed-parameter algorithm for the directed feedback vertex set problem
AU - Chen, Jianer
AU - Liu, Yang
AU - Lu, Songjian
AU - O'Sullivan, Barry
AU - Razgon, Igor
PY - 2008
Y1 - 2008
N2 - The (parameterized) FEEDBACK VERTEX SET problem on directed graphs, which we refer to as the DFVS problem, is defined as follows: given a directed graph G and a parameter κ, either construct a feedback vertex set of at most κ vertices in G or report that no such set exists. Whether or not the DFVS problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(κ)nO(1) for some function f. in this paper we develop new algorithmic techniques that result in an algorithm with running time 4κκ!nO(1) for the DFVS problem, thus showing that this problem is fixed-parameter tractable.
AB - The (parameterized) FEEDBACK VERTEX SET problem on directed graphs, which we refer to as the DFVS problem, is defined as follows: given a directed graph G and a parameter κ, either construct a feedback vertex set of at most κ vertices in G or report that no such set exists. Whether or not the DFVS problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(κ)nO(1) for some function f. in this paper we develop new algorithmic techniques that result in an algorithm with running time 4κκ!nO(1) for the DFVS problem, thus showing that this problem is fixed-parameter tractable.
KW - Algorithms
UR - https://www.scopus.com/pages/publications/57049178481
U2 - 10.1145/1374376.1374404
DO - 10.1145/1374376.1374404
M3 - Conference proceeding
AN - SCOPUS:57049178481
SN - 9781605580470
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 177
EP - 186
BT - STOC'08
PB - Association for Computing Machinery (ACM)
T2 - 40th Annual ACM Symposium on Theory of Computing, STOC 2008
Y2 - 17 May 2008 through 20 May 2008
ER -