Finite convergence of sum-of-squares hierarchies for the stability number of a graph
Luis Felipe Vargas  1@  , Monique Laurent  1, 2@  
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
Online user: 2 Privacy
Loading...