מירב זהבי

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∖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.