Kernels for deletion to classes of acyclic digraphs

Abstract

Given a digraph D and an integer k, Directed Feedback Vertex Set (DFVS) asks whether there exists a set of vertices S of size at most k such that F=D(set minus)S is DAG. 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 light on the kernelization complexity of DFVS, a well-known open problem in Parameterized Complexity. We improve the kernel sizes of Out-Forest Vertex Deletion Set from O(k³) to O(k²) and of Pumpkin Vertex Deletion Set from O(k¹⁸) to O(k³). We also prove that the former kernel size is tight under certain complexity theoretic assumptions.