Bivariate complexity analysis of Almost Forest Deletion

In this paper we study a generalization of classic Feedback Vertex Set problem in the realm of multivariate complexity analysis. We say that a graph F is an l-forest if we can delete at most l edges from F to get a forest. That is, F is at most l edges away from being a forest. In this paper we introduce the Almost Forest Deletion problem, where given a graph G and integers k and l, the question is whether there exists a subset of at most k vertices such that its deletion leaves us an l-forest. We show that this problem admits an algorithm with running time 2O(k+l)nO(1) and a kernel of size O(kl(k+l)). We also show that the problem admits a 2O(tw)nO(1) algorithm on bounded treewidth graphs, using which we design a subexponential algorithm for the problem on planar graphs.