Computational complexity of minimum P<inf>4</inf> vertex cover problem for regular and K <inf>1, 4</inf>-free graphs

In VCP4 problem, it is asked to find a set S⊆V of minimum size such that G[V\S] contains no path on 4 vertices, in a given graph G=(V,E). We prove that it is APX-complete for 3-regular graphs as well as 3-regular bipartite graphs. We show that a greedy based algorithm approximates VCP4 within a factor of 2 for regular graphs. We also show that VCP4 is APX-complete for K1, 4-free graphs and a local ratio based algorithm generates a solution which is within a factor of 3.