TY - JOUR

T1 - Exactness of Parrilo's conic approximations for copositive matrices >> and associated low order bounds for the stability number of a graph

AU - Laurent, Monique

AU - Vargas, Luis

PY - 2023/5

Y1 - 2023/5

N2 - 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≥0K(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ć and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.

AB - 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≥0K(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ć and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.

U2 - 10.1287/moor.2022.1290

DO - 10.1287/moor.2022.1290

M3 - Article

SN - 0364-765X

VL - 48

SP - 1017

EP - 1043

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 2

ER -