A fixed-parameter algorithm for the directed feedback vertex set problem
A fixed-parameter algorithm for the directed feedback vertex set problem
复制标题
DOI：
10.1145/1374376.1374404
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Jianer Chen;Yang Liu;Songjian Lu;B. O’Sullivan;Igor Razgon
中科院分区：
文献类型：
--
作者：
Jianer Chen;Yang Liu;Songjian Lu;B. O’Sullivan;Igor Razgon
有向图上的（参数化的）反馈顶点集问题，我们称之为dfvs问题，定义如下：给定有向图G和参数k，要么在G中构造一个至多k个顶点的反馈顶点集，要么报告不存在这样的集。dfvs问题是否是固定参数可处理的一直是参数化计算和复杂性中众所周知的公开问题，即，问题是否可以在时间f（k）nO（1）中解决，对于某个函数f。在本文中，我们开发了新的算法技术，导致运行时间为4k k！dfvs问题的nO（1），从而表明该问题是固定参数可处理的。
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 k, either construct a feedback vertex set of at most k 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(k)nO(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! nO(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.