Strong and weak edges of a graph and linkages with the vertex cover problem

In this paper we show that the problem of identifying an edge (i,j)(i,j) of a graph GG such that there exists an optimal vertex cover SS of GG containing exactly one of the vertices ii and jj is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee 2−11+σ, where σσ is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge (i,j)(i,j) such that there exists an optimal vertex cover containing both vertices ii and jj is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of σσ. We also obtain linear programming representations of the vertex cover problem on special graphs.