B. Bergnougnoux, E. Eiben,R. Ganian, S. Ordyniak, M. Ramanujan:

"Towards a Polynomial Kernel for Directed Feedback Vertex Set";

Talk: Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, Aalborg Denmark; 2017-08-21 - 2017-08-25; in: "Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science", Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, (2017), ISBN: 978-3-95977-046-0; 1 - 15.

In the Directed Feedback Vertex Set (DFVS) problem, the input is

a directed graph $D$ and an integer $k$. The objective is to determine

whether there exists a set of at most $k$ vertices intersecting every

directed cycle of $D$. DFVS was shown to be fixed-parameter tractable when

parameterized by solution size by Chen, Liu, Lu, O'Sullivan and

Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this

problem has become one of the largest open problems in the area of parameterized

algorithmics.

Since this problem has remained open in spite of the best efforts of a number

of prominent researchers and pioneers in the field, a natural step forward

is to study the kernelization complexity of DFVS parameterized

by a natural larger parameter. In this paper, we study

DFVS parameterized by the feedback vertex

set number of the underlying undirected graph. We provide

two main contributions: a polynomial kernel for this problem on general

instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

Created from the Publication Database of the Vienna University of Technology.