[Zurück]

B. Bergougnoux, E. Eiben, R. Ganian, S. Ordyniak, M. Ramanujan:
"Towards a Polynomial Kernel for Directed Feedback VertexSet";
Algorithmica, 82 (2020), S. 1 - 21.

In theDirected Feedback Vertex Set (DFVS)problem, the input is a directedgraphDand an integerk. The objective is to determine whether there exists a setof at mostkvertices intersecting every directed cycle ofD. DFVS was shown tobe fixed-parameter tractable when parameterized by solution size by Chen et al. (JACM 55(5):177-186, 2008); since then, the existence of a polynomial kernel for thisproblem has become one of the largest open problems in the area of parameterizedalgorithmics. Since this problem has remained open in spite of the best efforts ofa number of prominent researchers and pioneers in the field, a natural step forwardis to study the kernelization complexity ofDFVSparameterized by a naturallargerparameter. In this paper, we study DFVS parameterized by the feedback vertex setnumber of the underlyingundirected graph. We provide two main contributions: apolynomial kernel for this problem on general instances, and a linear kernel for thecase where the input digraph is embeddable on a surface of bounded genus.

http://dx.doi.org/10.1007/s00453-020-00777-5

https://publik.tuwien.ac.at/files/publik_293794.pdf