A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem Conference Paper uri icon

abstract

  • 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. Copyright 2008 ACM.

name of conference

  • Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008

published proceedings

  • STOC'08: PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING

author list (cited authors)

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

complete list of authors

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

publication date

  • December 2008