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.