TY - GEN

T1 - A faster parameterized algorithm for pseudoforest deletion

AU - Bodlaender, Hans L.

AU - Ono, Hirotaka

AU - Otachi, Yota

N1 - Publisher Copyright:
© 2016 Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi.

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.

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

UR - http://www.scopus.com/inward/citedby.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

T3 - Leibniz International Proceedings in Informatics, LIPIcs

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

A2 - Guo, Jiong

A2 - Hermelin, Danny

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

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

Y2 - 24 August 2016 through 26 August 2016

ER -