A 2-approximation algorithm for the vertex cover P₄ problem in cubic graphs

Abstract

A subset F of vertices of a graph G is called a vertex cover P_k 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 P_k set in G. The vertex cover P_k (VCP_k) problem is to find a minimum vertex cover P_k set. It is easy to see that the VCP₂ problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP₄ problem in cubic graphs. The paper proves that the VCP₄ problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ₄(G) for cubic graphs and propose a 2-approximation algorithm for the VCP₄ problem in cubic graphs.

Keywords:

• combinatorial optimization
• vertex cover P₄ problem
• approximation algorithm
• cubic graph
• sharp lower and upper bounds

2010 AMS Subject Classifications:

• 05C85
• 05C70

Acknowledgement

This work was supported by the National Natural Science Foundation of China (No. 11201021). We thank the editor and the reviewers for their valuable comments that greatly helped us to improve the quality of the manuscript.