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 ϑ(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.

• View at Publisher

Full Text ( Final Version , 1mb )

See Also
techReport Exactness of Parrilo's conic approximations for copositive matrices and associated low order bounds for the stability number of a graph M. Laurent (Monique) and L.F. Vargas (Luis)