Linear-time algorithms for eliminating claws in graphs

BONOMO-BRABERMAN, FLAVIA; NASCIMENTO, JULLIANO R.; OLIVEIRA, FABIANO S.; SOUZA, UÉVERTON S.; SZWARCFITER, JAYME L.

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

John Wiley and Sons Inc

Año: 2024 vol. 31 p. 296 - 315

0969-6016

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.