Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph
Monique Laurent, Luis Felipe Vargas · Mathematics of Operations Research · 2022
De Klerk and Pasechnik introduced in 2002 semidefinite bounds [Formula: see text] for the stability number [Formula: see text] of a graph G and conjectured their exactness at order [Formula: see text]. These bounds rely on the conic approximations [Formula: see text] introduced by Parrilo in 2000 for the copositive cone [Formula: see text]. 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 [Formula: see text] 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 [Formula: see text]. We investigate the graphs for which the bound of order r≤1 is exact: we algorithmically reduce testing exactness of [Formula: see text] to acritical graphs, we characterize the critical graphs with [Formula: see text] exact, and we exhibit graphs for which exactness of [Formula: see text] 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].