Parameterised Algorithms for Deletion to Classes of DAGs

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 such that F = D - S is an acyclic digraph. In a recent paper, Mnich and van Leeuwen [ STACS 2016] studied the kernelization complexity of DFVS with an additional restriction on Fnamely that F must be an out- forest, an out- tree, or a ( directed) pumpkin- with an objective of shedding some light on the kernelization complexity of the DFVS problem, a well known open problem in the area. The vertex deletion problems corresponding to obtaining an out- forest, an out- tree, or a ( directed) pumpkin are OUT- FOREST/ OUT- TREE/ PUMPKIN VERTEX DELETION SET, respectively. They showed that OUT- FOREST/ OUT- TREE/ PUMPKIN VERTEX DELETION SET admit polynomial kernels. Another open problem regarding DFVS is that, does DFVS admit an algorithm with running time 2 O( k) n O( 1)? We complement the kernelization programme of Mnich and van Leeuwen by designing fast FPT algorithms for the above mentioned problems. In particular, we design an algorithm for OUT- FOREST VERTEX DELETION SET that runs in time O( 2.732kn O( 1)) and algorithms for PUMPKIN/ OUT- TREE VERTEX DELETION SET that runs in time O( 2.562kn O( 1)). As a corollary of our FPT algorithms and the recent result of Fomin et al. [ STOC 2016] which gives a relation between FPT algorithms and exact algorithms, we get exact algorithms for OUT- FOREST/ OUT- TREE/ PUMPKIN VERTEX DELETION SET that run in time O( 1.633nn O( 1)), O( 1.609nn O( 1)) and O( 1.609nn O( 1)), respectively.