Optimization Online


Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

Nebojsa Gvozdenovic (nebojsa***at***cwi.nl)
Monique Laurent (monique***at***cwi.nl)

Abstract: Lov\' asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre [2001] and by de Klerk and Pasechnik [2002], which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in $\alpha(G)$ steps as it refines the hierarchy of Lov\'asz and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after $\alpha(G)$ steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.

Keywords: Stability number of a graph, semidefinite programming, sum of squares of polynomials

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: https://www.springerlink.com/content/n765028367u34083/resource-secured/?target=fulltext.pdf


Entry Submitted: 06/27/2005
Entry Accepted: 06/27/2005
Entry Last Modified: 01/12/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society