2026-08-17T10:38:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6924 2024-03-12T11:58:49Z ddc:004 open_access

A Faster Parameterized Algorithm for Pseudoforest Deletion Bodlaender, Hans L. Ono, Hirotaka Otachi, Yota pseudoforest deletion graph class width parameter parameterized complexity 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. [MFCS 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Hirotaka Ono and Yota Otachi 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.7 urn:nbn:de:0030-drops-69246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode