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.IPEC.2016.7
URN: urn:nbn:de:0030-drops-69246
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6924/
Go to the corresponding LIPIcs Volume Portal

Bodlaender, Hans L. ; Ono, Hirotaka ; Otachi, Yota

A Faster Parameterized Algorithm for Pseudoforest Deletion

pdf-format:
LIPIcs-IPEC-2016-7.pdf (0.5 MB)

Abstract

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

BibTeX - Entry

@InProceedings{bodlaender_et_al:LIPIcs:2017:6924,
  author =	{Hans L. Bodlaender and Hirotaka Ono and Yota Otachi},
  title =	{{A Faster Parameterized Algorithm for Pseudoforest Deletion}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6924},
  URN =		{urn:nbn:de:0030-drops-69246},
  doi =		{10.4230/LIPIcs.IPEC.2016.7},
  annote =	{Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity}
}

Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

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