2022-04-25
Finite convergence of sum-of-squares hierarchies for the stability number of a graph
Publication
Publication
SIAM Journal on Optimization , Volume 32 - Issue 2 p. 491- 518
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 the Motzkin--Straus formulation and showing that their number is finite precisely when G is acritical. Moreover we show that these results hold in the general setting of the weighted stable set problem for graphs equipped with positive node weights. In addition, 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.
Additional Metadata | |
---|---|
, , , , , , , , , | |
doi.org/10.1137/21M140345X | |
SIAM Journal on Optimization | |
Polynomial Optimization, Efficiency through Moments and Algebra | |
Organisation | CWI management |
Laurent, M., & Vargas, L. (2022). Finite convergence of sum-of-squares hierarchies for the stability number of a graph. SIAM Journal on Optimization, 32(2), 491–518. doi:10.1137/21M140345X |