De Klerk and Pasechnik introduced in 2002 semidefinite bounds ϑ(r)(G)(r≥0) for the stability number α(G) of a graph G and conjectured their exactness at order r=α(G)−1. These bounds rely on the conic approximations K(r)n introduced by Parrilo in 2000 for the copositive cone COPn. 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 K(r)n 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≥6. We investigate the graphs for which the bound of order r≤1 is exact: we algorithmically reduce testing exactness of ϑ(0) to acritical graphs, we characterize the critical graphs with ϑ(0) exact, and we exhibit graphs for which exactness of ϑ(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.

, , , , , ,
Mathematics of Operations Research
Polynomial Optimization, Efficiency through Moments and Algebra
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Laurent, M., & Vargas, L. (2022). Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph. Mathematics of Operations Research, 1–27. doi:10.1287/moor.2022.1290