Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph

De Klerk and Pasechnik introduced in 2002 semidefinite bounds ${\vartheta }^{(r)}(G)(r\ge 0)$ for the stability number $\alpha (G)$ of a graph G and conjectured their exactness at order $r=\alpha (G)-1$. These bounds rely on the conic approximations ${\mathcal{K}}_n^{(\mathit{r})}$ introduced by Parrilo in 2000 for the copositive cone ${\text{COP}}_n$. A difficulty in the convergence analysis of the bounds is the bad behavior of Parrilo’s cones under adding a zero row/column: when applied to a matrix not in ${\mathcal{K}}_n^{(r)}$ this gives a matrix that does not lie in any of Parrilo’s cones, thereby showing that their union is a strict subset of the copositive cone for any $n\ge 6$. We investigate the graphs for which the bound of order r≤1 is exact: we algorithmically reduce testing exactness of ${\vartheta }^{(0)}$ to acritical graphs, we characterize the 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 posed by Gvozdenović and Laurent in 2007, which, if true, would have implied the above conjecture by de Klerk and Pasechnik.

Funding: This work is supported by the European Union’s Framework Programme for Research and Innovation Horizon 2020 under the Marie Skłodowska-Curie Actions Grant Agreement Polynomial Optimization, Efficiency through Moments and Algebra [Grant 813211].