License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.6
URN: urn:nbn:de:0030-drops-67777
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6777/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Akanksha ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

Kernels for Deletion to Classes of Acyclic Digraphs

pdf-format:
LIPIcs-ISAAC-2016-6.pdf (0.5 MB)

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 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^3) to O(k^2) and of Pumpkin Vertex Deletion Set from O(k^18) to O(k^3). We also prove that the former kernel size is tight under certain complexity theoretic assumptions.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2016:6777,
  author =	{Akanksha Agrawal and Saket Saurabh and Roohani Sharma and Meirav Zehavi},
  title =	{{Kernels for Deletion to Classes of Acyclic Digraphs}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6777},
  URN =		{urn:nbn:de:0030-drops-67777},
  doi =		{10.4230/LIPIcs.ISAAC.2016.6},
  annote =	{Keywords: out-forest, pumpkin, parameterized complexity, kernelization}
}

Keywords: out-forest, pumpkin, parameterized complexity, kernelization
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI