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

Abstract

We introduce the vertex cover P n (VCP n ) problem, that is, the problem of finding a minimum weight set F⊂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 VCP n problem is NP-hard for any integer n≥2. Then we restrict our attention to the VC P3 problem and give a 2-approximation algorithm using the primal-dual method. © 2011 Elsevier B.V. All rights reserved.