Finite convergence of sum-of-squares hierarchies for the stability number of a graph
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916098329280512 |
|---|---|
| author | Laurent, Monique Vargas, Luis Felipe |
| author_facet | Laurent, Monique Vargas, Luis Felipe |
| contents | We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $α(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [{\em 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\setminus 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_01574 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Finite convergence of sum-of-squares hierarchies for the stability number of a graph Laurent, Monique Vargas, Luis Felipe Optimization and Control We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $α(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [{\em 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\setminus 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. |
| title | Finite convergence of sum-of-squares hierarchies for the stability number of a graph |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2103.01574 |