A faster parameterized algorithm for pseudoforest deletion

H.L. Bodlaender; H. Ono; Y. Otachi

doi:10.4230/LIPIcs.IPEC.2016.7

A faster parameterized algorithm for pseudoforest deletion

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

152 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^knk^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^kn^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
Title of host publication	11th International Symposium on Parameterized and Exact Computation, IPEC 2016
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	12
Volume	63
ISBN (Electronic)	9783959770231
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2016.7
Publication status	Published - 1 Feb 2017
Event	11th International Symposium on Parameterized and Exact Computation, IPEC 2016 - Aarhus, Denmark Duration: 24 Aug 2016 → 26 Aug 2016 Conference number: 11 http://conferences.au.dk/algo16/ipec

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	63
ISSN (Print)	1868-8969

Conference

Conference	11th International Symposium on Parameterized and Exact Computation, IPEC 2016
Abbreviated title	IPEC 2016
Country/Territory	Denmark
City	Aarhus
Period	24/08/16 → 26/08/16
Internet address	http://conferences.au.dk/algo16/ipec

Keywords

Graph class
Parameterized complexity
Pseudoforest deletion
Width parameter

Access to Document

10.4230/LIPIcs.IPEC.2016.7Licence: CC BY

Publishers versionFinal published version, 520 KB

Cite this

Bodlaender, H. L., Ono, H., & Otachi, Y. (2017). A faster parameterized algorithm for pseudoforest deletion. In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016 (Vol. 63). Article 7 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 63). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2016.7

@inproceedings{df221ac07d99453290b1e83f36b74875,

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(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.",

keywords = "Graph class, Parameterized complexity, Pseudoforest deletion, Width parameter",

author = "H.L. Bodlaender and H. Ono and Y. Otachi",

year = "2017",

month = feb,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2016.7",

language = "English",

volume = "63",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

booktitle = "11th International Symposium on Parameterized and Exact Computation, IPEC 2016",

note = "11th International Symposium on Parameterized and Exact Computation, IPEC 2016, IPEC 2016 ; Conference date: 24-08-2016 Through 26-08-2016",

url = "http://conferences.au.dk/algo16/ipec",

}

Bodlaender, HL, Ono, H & Otachi, Y 2017, A faster parameterized algorithm for pseudoforest deletion. in 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. vol. 63, 7, Leibniz International Proceedings in Informatics (LIPIcs), vol. 63, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark, 24/08/16. https://doi.org/10.4230/LIPIcs.IPEC.2016.7

A faster parameterized algorithm for pseudoforest deletion. / Bodlaender, H.L.; Ono, H.; Otachi, Y.
11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Vol. 63 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 7 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 63).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A faster parameterized algorithm for pseudoforest deletion

AU - Bodlaender, H.L.

AU - Ono, H.

AU - Otachi, Y.

N1 - Conference code: 11

PY - 2017/2/1

Y1 - 2017/2/1

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

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

KW - Graph class

KW - Parameterized complexity

KW - Pseudoforest deletion

KW - Width parameter

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

U2 - 10.4230/LIPIcs.IPEC.2016.7

DO - 10.4230/LIPIcs.IPEC.2016.7

M3 - Conference contribution

AN - SCOPUS:85014711805

VL - 63

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 11th International Symposium on Parameterized and Exact Computation, IPEC 2016

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 11th International Symposium on Parameterized and Exact Computation, IPEC 2016

Y2 - 24 August 2016 through 26 August 2016

ER -

A faster parameterized algorithm for pseudoforest deletion

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this