2026-08-10T19:40:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8112 2024-03-06T10:40:53Z ddc:004 open_access

Towards a Polynomial Kernel for Directed Feedback Vertex Set Bergougnoux, Benjamin Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Ramanujan, M. S. parameterized algorithms kernelization (directed) feedback vertex set 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bergougnoux and Eduard Eiben and Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.36 urn:nbn:de:0030-drops-81126 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.36 eng https://creativecommons.org/licenses/by/3.0/legalcode