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

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.

Citation

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