[Back]

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; 08-21-2017 - 08-25-2017; 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.