A factor 2 approximation algorithm for the vertex cover P ³ problem

Abstract

We consider 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 restrict our attention to the VCP 3 problem and give a 2-approximation algorithm using the technique of layering. © 2011 Elsevier B.V.