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

作者：Li, Yuchao; Tu, Jianhua^*

来源：International Journal of Computer Mathematics, 2014, 91(10): 2103-2108.

DOI：10.1080/00207160.2014.881476

• 05C85
• 05C70
• combinatorial optimization
• cubic graph
• approximation algorithm
• sharp lower and upper bounds
• vertex cover P-4 problem

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 psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The vertex cover P-k (VCPk) problem is to find a minimum vertex cover P-k 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 psi(4)(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.

• 出版日期2014-10-3
• 单位北京化工大学