## Abstract

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
^{(}
_{n}
^{r)} introduced by Parrilo in 2000 for the copositive cone 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 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 ≥ 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.

Original language | English |
---|---|

Pages (from-to) | 1017-1043 |

Journal | Mathematics of Operations Research |

Volume | 48 |

Issue number | 2 |

DOIs | |

Publication status | Published - May 2023 |

## Keywords

- Shor relaxation
- a-critical graph
- copositive matrix
- polynomial optimization
- semidefinite programming
- stable set problem
- sum-of-squares polynomial