We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph G with n vertices and a positive integer k, the algorithm constructs a family of at least k/p(k) disjoint c...
详细信息
ISBN:
(纸本)9783540734192
We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph G with n vertices and a positive integer k, the algorithm constructs a family of at least k/p(k) disjoint cycles of G if the graph G has a family of at least k disjoint cycles (and otherwise may still produce a solution, or just report failure). Here p is a computable function such that k/p(k) is nondecreasing and unbounded. The running time of our algorithm is polynomial. The directed vertex disjoint cycle problem is hard for the parameterizedcomplexity class W[1], and to the best of our knowledge our algorithm is the first fpt approximation algorithm for a natural W[1]-hard problem.
Most parameterizedcomplexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem(the so-called weighted satisfiability problem). For example, Downey and Fellow'sW-hierarc...
详细信息
Most parameterizedcomplexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem(the so-called weighted satisfiability problem). For example, Downey and Fellow'sW-hierarchy is of this form. But there are also classes such as the A-hierarchy, that are more naturally characterised in terms of model-checking problems for certain fragments of first-order logic. Downey, Fellows, and Regan(1998) were the first to establish a connection between the two formalisms by giving a characterisation of the W-hierarchy in terms of first-order model-checking problems. We improve their result and then prove a similar correspondence between weighted satisfiability and model-checking problems for the A-hierarchy and the W*-hierarchy. Thus we obtain very uniform characterisations of many of the most important parameterizedcomplexity classes in both formalisms. Our results can be used to give new, simple proofs of some of the core results of structural parameterized complexity theory.
暂无评论