A faster parameterized algorithm for PSEUDOFOREST DELETION
Publication date
2018-02-19
Authors
Bodlaender, H.L.
Ono, Hirotaka
Otachi, Yota
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
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. (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
Feedback vertex set, Fixed parameter tractability, Graph algorithms, Pseudoforest, Treewidth, Taverne, Discrete Mathematics and Combinatorics, Applied Mathematics
Citation
Bodlaender, H L, Ono, H & Otachi, Y 2018, 'A faster parameterized algorithm for PSEUDOFOREST DELETION', Discrete Applied Mathematics, vol. 236, pp. 42-56. https://doi.org/10.1016/j.dam.2017.10.018