Please use this identifier to cite or link to this item:
Title: Approximation of the stability number of a graph via copositive programming
Authors: Klerk, Etienne de.
Pasechnik, Dmitrii V.
Keywords: DRNTU::Science::Mathematics::Applied mathematics
Issue Date: 2002
Source: Klerk, E. D., & Pasechnik, D. V. (2002). Approximation of the stability number of a graph via copositive programming. SIAM journal on optimization, 12(4), 875-892.
Series/Report no.: SIAM journal on optimization
Abstract: 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.
DOI: 10.1137/S1052623401383248
Rights: © 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:]. 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.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
19. Approximation of the stability number of a graph via copositive programming.pdf195.58 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.