Towards a Polynomial Kernel for Directed Feedback Vertex Set
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan · Algorithmica · 2020
Abstract In theDirected Feedback Vertex Set (DFVS)problem, the input is a directed graphDand an integerk. The objective is to determine whether there exists a set of at mostkvertices intersecting every directed cycle ofD. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen et al. (J ACM 55(5):177–186, 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 ofDFVSparameterized by a naturallargerparameter. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlyingundirected 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.