Approximation of the stability number of a graph via copositive programming.
Klerk, Etienne de.
Pasechnik, Dmitrii V.
Date of Issue2002
School of Physical and Mathematical Sciences
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 semideﬁnite 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 semideﬁnite programs of increasing size (liftings). The latter idea is based on recent work by Parrilo [Structured Semideﬁnite 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 ﬁrst 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.
SIAM journal on optimization
© 2002 SIAM This paper was published in SIAM Journal on Optimization and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at: [DOI: http://dx.doi.org/10.1137/S1052623401383248]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.