Finite convergence of sum-of-squares hierarchies for the stability number of a graph

We investigate a hierarchy of semidefinite bounds ϑ(r)(G) for the stability number α(G) of a graph G, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to α(G) in r = α(G) − 1 steps. Even the weaker conjecture claiming finite convergence is still open. We establish links between this hierarchy and sum-of-squares hierarchies based on the Motzkin-Straus formulation of α(G), which we use to show finite convergence when G is acritical, i.e., when α(G \ e) = α(G) for all edges e of G. This relies, in particular, on understanding the structure of the minimizers of Motzkin-Straus formulation and showing that their number is finite precisely when G is acritical. As a byproduct we show that deciding whether a standard quadratic program has finitely many minimizers does not admit a polynomial-time algorithm unless P=NP.

• View at arXiv

Free Full Text ( Final Version , 368kb )

See Also
article Finite convergence of sum-of-squares hierarchies for the stability number of a graph M. Laurent (Monique) and L.F. Vargas (Luis)