A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem Academic Article uri icon

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.

published proceedings

  • JOURNAL OF THE ACM

altmetric score

  • 6

author list (cited authors)

  • Chen, J., Liu, Y., Lu, S., O'Sullivan, B., & Razgon, I.

citation count

  • 146

complete list of authors

  • Chen, Jianer||Liu, Yang||Lu, Songjian||O'Sullivan, Barry||Razgon, Igor

publication date

  • October 2008