A faster parameterized algorithm for PSEUDOFOREST DELETION

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

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
79 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(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. (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.

Original languageEnglish
Pages (from-to)42-56
Number of pages15
JournalDiscrete Applied Mathematics
Volume236
DOIs
Publication statusPublished - 19 Feb 2018

Keywords

  • Feedback vertex set
  • Fixed parameter tractability
  • Graph algorithms
  • Pseudoforest
  • Treewidth

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

Cite this