2026-07-22T00:15:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6777 2024-03-06T10:38:51Z ddc:004 open_access

Kernels for Deletion to Classes of Acyclic Digraphs Agrawal, Akanksha Saurabh, Saket Sharma, Roohani Zehavi, Meirav out-forest pumpkin parameterized complexity kernelization In the Directed Feedback Vertex Set (DFVS) problem, we are given a digraph D on n vertices and a positive integer k and the objective is to check whether there exists a set of vertices S of size at most k such that F = D - S is a directed acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016] considered the kernelization complexity of DFVS with an additional restriction on F, namely that F must be an out-forest (Out-Forest Vertex Deletion Set), an out-tree (Out-Tree Vertex Deletion Set), or a (directed) pumpkin (Pumpkin Vertex Deletion Set). Their objective was to shed some light on the kernelization complexity of the DFVS problem, a well known open problem in the area of Parameterized Complexity. In this article, we improve the kernel sizes of Out-Forest Vertex Deletion Set from O(k^3) to O(k^2) and of Pumpkin Vertex Deletion Set from O(k^18) to O(k^3). We also prove that the former kernel size is tight under certain complexity theoretic assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Saket Saurabh and Roohani Sharma and Meirav Zehavi 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.6 urn:nbn:de:0030-drops-67777 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.6 eng https://creativecommons.org/licenses/by/3.0/legalcode