Finite convergence of sum-of-squares hierarchies for the stability number of a graph
1 : cwi
2 : Tilburg University
Computing the stability number of a graph is an NP-hard problem and some approximations via semidefinite optimization have been developed. One of them is a hierarchy proposed by de Klerk and Pasechnik by following an idea given by Parrilo for approximating problems over the copositive. One open question asks for the finite convergence of this hierarchy. We prove finite convergence for the class of acritical graphs. Our analysis relies on exploiting a link to the Lasserre hierarchy for the Motzkin-Straus formulation and using a known sufficient condition for its finite convergence. As an application we show that deciding whether a standard quadratic problem has finitely many minimizers is hard
- Poster