A faster parameterized algorithm for PSEUDOFOREST DELETION

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)nk(0(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(0(1))-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n. (C) 2017 Elsevier B.V. All rights reserved.