A faster parameterized algorithm for pseudoforest deletion

H.L. Bodlaender, H. Ono, Y. Otachi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
111 Downloads (Pure)

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(3knkO(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.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

Original languageEnglish
Title of host publication11th International Symposium on Parameterized and Exact Computation, IPEC 2016
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
Volume63
ISBN (Electronic)9783959770231
DOIs
Publication statusPublished - 1 Feb 2017
Event11th International Symposium on Parameterized and Exact Computation (IPEC 2016) - Aarhus, Denmark
Duration: 24 Aug 201626 Aug 2016
Conference number: 11
http://conferences.au.dk/algo16/ipec

Conference

Conference11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Abbreviated titleIPEC 2016
CountryDenmark
CityAarhus
Period24/08/1626/08/16
Internet address

Keywords

  • Graph class
  • Parameterized complexity
  • Pseudoforest deletion
  • Width parameter

Fingerprint Dive into the research topics of 'A faster parameterized algorithm for pseudoforest deletion'. Together they form a unique fingerprint.

Cite this