Approximation of the stability number of a graph via copositive programming

Lovasz and Schrijver [ SIAM J. Optim., 1 ( 1991), pp. 166 190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semidefinite programs ( SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the stability number can be computed as the solution of a conic linear program ( LP) over the cone of copositive matrices. Subsequently, we show how to approximate the copositive cone ever more closely via a hierarchy of linear or semidefinite programs of increasing size (liftings). The latter idea is based on recent work by Parrilo [ Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000]. In this way we can compute the stability number ( G) of any graph G ( V, E) after at most ( G) 2 successive liftings for the LP-based approximations. One can compare this to the n-alpha(G)-1 bound for the LP-based lift-and-project scheme of Lovasz and Schrijver. Our approach therefore requires fewer liftings for families of graphs where alpha(G) < O (√n). We show that the first SDP-based approximation for ( G) in our series of increasingly tight approximations coincides with the θ'-function of Schrijver [IEEE Trans. Inform. Theory, 25 ( 1979), pp. 425 429]. We further show that the second approximation is tight for complements of triangle-free graphs and for odd cycles.