Back to Search
Start Over
Parameterised Algorithms for Deletion to Classes of DAGs.
- Source :
-
Theory of Computing Systems . Nov2018, Vol. 62 Issue 8, p1880-1909. 30p. - Publication Year :
- 2018
-
Abstract
- 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 F—namely 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 2O(k)nO(1)<inline-graphic></inline-graphic>? 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.732knO(1))<inline-graphic></inline-graphic> and algorithms for PUMPKIN/OUT-TREE VERTEX DELETION SET that runs in time O(2.562knO(1))<inline-graphic></inline-graphic>. 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.633nnO(1))<inline-graphic></inline-graphic>, O(1.609nnO(1))<inline-graphic></inline-graphic> and O(1.609nnO(1))<inline-graphic></inline-graphic>, respectively. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 62
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 131704538
- Full Text :
- https://doi.org/10.1007/s00224-018-9852-7