Given a graph G=(V,E), a non-negative weight function c, and a subset of nodes, S. We consider a generalization of the vertex cover problem over G in which the objective is to find a vertex cover (if available) of minimum cost that does not use any node of S. We show that this generalization of vertex cover problem preserves half integrality property and thereby give a 2-optimal approximation algorithm.
