Dekel Tsur

In the r-PSEUDOFOREST DELETION problem, the input is a graph G and integers k,r, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph in which every connected component can be made into a tree by deleting at most r edges. In this paper we give an O^⁎((8r+1)^k)-time algorithm for r-PSEUDOFOREST DELETION for every r≥1.