  We study the problem of deleting a minimum cost set of vertices from a given
vertex-weighted graph in such a way that the resulting graph has no induced
path on three vertices. This problem is often called cluster vertex deletion in
the literature and admits a straightforward 3-approximation algorithm since it
is a special case of the vertex cover problem on a 3-uniform hypergraph.
Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm
for the unweighted version of the problem. Our main result is a
9/4-approximation algorithm for arbitrary weights, using the local ratio
technique. We further conjecture that the problem admits a 2-approximation
algorithm and give some support for the conjecture. This is in sharp contrast
with the fact that the similar problem of deleting vertices to eliminate all
triangles in a graph is known to be UGC-hard to approximate to within a ratio
better than 3, as proved by Guruswami and Lee.
