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 (2002) introduced the bounds ϑ(r)(G) (r ∈ N) for the stability number α(G) of a graph G and conjectured exactness at order α(G) − 1: ϑ(α(G)−1)(G) = α(G). These bounds rely on the conic approximations K(r) n by Parrilo (2000) for the copositive cone COPn. A difficulty in the convergence analysis of ϑ(r) is the bad behaviour of the cones K(r) n under adding a zero row/column: when applied to a matrix not in K(0) n this gives a matrix not in any K(r) n+1, thereby showing strict inclusion ⋃ r≥0 K(r) n ⊂ COPn for n ≥ 6. We investigate the graphs with ϑ(r)(G) = α(G) for r = 0, 1: we algorithmically reduce testing exactness of ϑ(0) to acritical graphs, we characterize 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 by Gvozdenovi´c and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.

• View at arXiv

Free Full Text ( Final Version , 420kb )

See Also
article 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)