מירב זהבי

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³) 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.