Bivariate Complexity Analysis of Almost Forest Deletion

Abstract

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 2^o(l+k)n^o(1) And A Kernel Of Size O(kl(k+l)). We Also Show That The Problem Admits A C^twn^o(1) Algorithm On Bounded Treewidth Graphs, Using Which We Design A Subexponential Algorithm For The Problem On Planar Graphs.