Exactness of Parrilo's conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

Abstract

De Klerk and Pasechnik (2002) introduced the bounds ${\vartheta }^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha (G)$ of a graph $G$ and conjectured exactness at order $\alpha (G)-1$: ${\vartheta }^{(\alpha (G)-1)}(G)=\alpha (G)$. These bounds rely on the conic approximations ${\mathcal{K}}_n^{(r)}$ by Parrilo (2000) for the copositive cone ${\text{COP}}_n$. A difficulty in the convergence analysis of ${\vartheta }^{(r)}$ is the bad behaviour of the cones ${\mathcal{K}}_n^{(r)}$ under adding a zero row/column: when applied to a matrix not in ${\mathcal{K}}_n^{(0)}$ this gives a matrix not in any ${\mathcal{K}}_{n+1}^{(r)}$, thereby showing strict inclusion ${\bigcup }_{r\ge 0}{\mathcal{K}}_n^{(r)}\subset {\text{COP}}_n$ for $n\ge 6$. We investigate the graphs with ${\vartheta }^{(r)}(G)=\alpha (G)$ for $r=0,1$: we algorithmically reduce testing exactness of ${\vartheta }^{(0)}$ to acritical graphs, we characterize critical graphs with ${\vartheta }^{(0)}$ exact, and we exhibit graphs for which exactness of ${\vartheta }^{(1)}$ is not preserved under adding an isolated node. This disproves a conjecture by Gvozdenović and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.