A faster parameterized algorithm for PSEUDOFOREST DELETION

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

Research output: Contribution to journalArticleAcademicpeer-review

49 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
JournalDiscrete Applied Mathematics
Volume236
DOIs
Publication statusPublished - 19 Feb 2018

Fingerprint

Parameterized Algorithms
Fast Algorithm
Polynomials
Connected Components
Graph in graph theory
Cycle
Polynomial
Integer

Keywords

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

Cite this

@article{53e5905595794504837a088f56a18594,
title = "A faster parameterized algorithm for PSEUDOFOREST DELETION",
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.",
keywords = "Feedback vertex set, Fixed parameter tractability, Graph algorithms, Pseudoforest, Treewidth",
author = "H.L. Bodlaender and H. Ono and Y. Otachi",
year = "2018",
month = "2",
day = "19",
doi = "10.1016/j.dam.2017.10.018",
language = "English",
volume = "236",
pages = "42--56",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

A faster parameterized algorithm for PSEUDOFOREST DELETION. / Bodlaender, H.L.; Ono, H.; Otachi, Y.

In: Discrete Applied Mathematics, Vol. 236, 19.02.2018, p. 42-56.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A faster parameterized algorithm for PSEUDOFOREST DELETION

AU - Bodlaender, H.L.

AU - Ono, H.

AU - Otachi, Y.

PY - 2018/2/19

Y1 - 2018/2/19

N2 - 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.

AB - 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.

KW - Feedback vertex set

KW - Fixed parameter tractability

KW - Graph algorithms

KW - Pseudoforest

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85036605615&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2017.10.018

DO - 10.1016/j.dam.2017.10.018

M3 - Article

AN - SCOPUS:85036605615

VL - 236

SP - 42

EP - 56

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -