An improved FPT algorithm for Almost Forest Deletion problem

Almost Forest Deletion problem (AFD) is a generalization of the Feedback Vertex Set problem, which decides whether there exist at most k vertices in a given graph G whose removal from G results in an l-forest, where k and l are two given non-negative integers, and an l-forest is a graph which can be transformed into a forest by deleting at most l edges. Based on the iterative compression technique, we study the iterative version of the AFD problem, called Almost Forest Deletion Disjoint Compression problem (AFDDC), which asks for a new l-forest deletion set X′ of size at most k for a given graph G that is disjoint with a given l-forest deletion set X of graph G for two given non-negative integers k and l. For the AFDDC problem, we develop some reduction rules to simplify a given instance, and give a new branching algorithm for the problem. A new branching measure is presented to evaluate the efficiency of the algorithm, which results in an algorithm of running time O⁎(4k+l). Based on the proposed algorithm for the AFDDC problem, a parameterized algorithm for the AFD problem with running time O⁎(5k4l) is presented, improving the previous result O⁎(5.0024(k+l)).