Polynomial kernels for deletion to classes of acyclic digraphs

We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

Subjects

directed feedback vertex/arc set

parameterized algorithms

kernels

DDC Class

004: Informatik

More Funding Information

Supported by ERC Starting Grant 306465 (BeyondWorstCase).

Lizenz

https://creativecommons.org/licenses/by/3.0/

Name

56-1.pdf

Size

655.36 KB

Format

Adobe PDF

Options

Polynomial kernels for deletion to classes of acyclic digraphs