THE LOVASZ THETA-FUNCTION AND A SEMIDEFINITE PROGRAMMING RELAXATION OF VERTEX COVER

Let vc(G) denote the minimum size of a vertex cover of a graph G = (V, E). It is well known that one can approximate vc(G) to within a factor of 2 in polynomial time; and despite considerable investigation, no ( 2 - epsilon)-approximation algorithm has been found for any epsilon > 0. Because of the many connections between the independence number alp ha(G) and the Lovasz theta function theta(G), and because vc(G) = \V\ - alpha(G), it is natural to ask how well \V\ - theta(G) approximates vc(G). It is not difficult to show that these quantities are within a factor of 2 of each other (\V\ - theta(G) is never less than the value of the canonical linear programming relaxation of vc(G)); our main re sult is that vc(G) can be more than (2 - epsilon) times \V\ - theta(G) for any epsilon > 0. We also investigate a stronger lower bound than \V\ - theta(G) for vc(G).