Linear-time algorithms for eliminating claws in graphs

Abstract

Since many (Formula presented.) -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a measure. Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is (Formula presented.) -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing (Formula presented.) executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is (Formula presented.) -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture.