A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
Yuchao Li, Jianhua Tu · International Journal of Computer Mathematics · 2014
A subset F of vertices of a graph G is called a vertex cover Pk set if every path of order k in G contains at least one vertex from F. Denote by ψk(G) the minimum cardinality of a vertex cover Pk set in G. The vertex cover Pk (VCPk) problem is to find a minimum vertex cover Pk set. It is easy to see that the VCP2 problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP4 problem in cubic graphs. The paper proves that the VCP4 problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ4(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.