Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874158 | Information Processing Letters | 2018 | 7 Pages |
Abstract
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)).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mugang Lin, Qilong Feng, Jianxin Wang, Jianer Chen, Bin Fu, Wenjun Li,