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

Nebojsa Gvozdenovic (nebojsacwi.nl)
Monique Laurent (moniquecwi.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

Download:

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

Modify/Update this entry