A primal-dual approximation algorithm for the vertex cover P-3 problem

作者：Tu, Jianhua^*; Zhou, Wenli

来源：Theoretical Computer Science, 2011, 412(50): 7044-7048.

DOI：10.1016/j.tcs.2011.09.013

• Combinatorial optimization
• Approximation algorithm
• Vertex cover P-n problem
• The primal-dual method

We introduce the vertex cover P-n (VCPn) problem, that is, the problem of finding a minimum weight set F subset of V such that the graph G[V - F] has no P-n, where P-n is a path with n vertices. The problem also has its application background. In this paper, we first show that the VCPn problem is NP-hard for any integer n >= 2. Then we restrict our attention to the VCP3 problem and give a 2-approximation algorithm using the primal-dual method.

• 出版日期2011-11-25
• 单位北京化工大学; IBM