Faster algorithms for 3-leaf power modification problems

Abstract In the 3-Leaf Power Vertex Deletion (resp., 3-Leaf Power Edge Deletion ) problem, the input is a graph G and an integer k , and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph that is a 3-leaf power. In this paper we give $$O^*(4.237^k)$$ -time algorithms for 3-Leaf Power Vertex Deletion and 3-Leaf Power Edge Deletion .