### 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 language | English |
---|---|

Pages (from-to) | 42-56 |

Journal | Discrete Applied Mathematics |

Volume | 236 |

DOIs | |

Publication status | Published - 19 Feb 2018 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*,

*236*, 42-56. https://doi.org/10.1016/j.dam.2017.10.018

}

*Discrete Applied Mathematics*, vol. 236, pp. 42-56. https://doi.org/10.1016/j.dam.2017.10.018

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

Research output: Contribution to journal › Article › Academic › peer-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 -