An improved FPT algorithm for Almost Forest Deletion problem uri icon

abstract

  • 2018 Elsevier B.V. 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 (4 k+l ). Based on the proposed algorithm for the AFDDC problem, a parameterized algorithm for the AFD problem with running time O (5 k 4 l ) is presented, improving the previous result O (5.0024 (k+l) ).

published proceedings

  • INFORMATION PROCESSING LETTERS

author list (cited authors)

  • Lin, M., Feng, Q., Wang, J., Chen, J., Fu, B., & Li, W.

citation count

  • 9

complete list of authors

  • Lin, Mugang||Feng, Qilong||Wang, Jianxin||Chen, Jianer||Fu, Bin||Li, Wenjun

publication date

  • August 2018