Computational complexity of minimum P4P4 vertex cover problem for regular and K1,4K1,4-free graphs

In VCP4 problem, it is asked to find a set S⊆VS⊆V of minimum size such that G[V∖S]G[V∖S] contains no path on 4 vertices, in a given graph G=(V,E)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,4K1,4-free graphs and a local ratio based algorithm generates a solution which is within a factor of 3.