A primal–dual approximation algorithm for the vertex cover P3 problem

We introduce the vertex cover Pn (VCPn) problem, that is, the problem of finding a minimum weight set F⊂V such that the graph G[V−F] has no Pn, where Pn 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.