Approximation of the Stability Number of a Graph via Copositive Programming

Lovász 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 - α(G) - 1 bound for the LP-based lift-and-project scheme of Lovász and Schrijver. Our approach therefore requires fewer liftings for families of graphs where a(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.