Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph

DOI10.1287/MOOR.2022.1290arXiv2109.12876WikidataQ114058146 ScholiaQ114058146MaRDI QIDQ6199282FDOQ6199282

Authors: Monique Laurent, Luis Felipe Vargas 

Publication date: 23 February 2024

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: De Klerk and Pasechnik (2002) introduced the bounds $varthet{a}^{(r)}(G)$ ($rinmathbbN$) for the stability number $alpha(G)$ of a graph $G$ and conjectured exactness at order $alpha(G)-1$: $varthet{a}^{(alpha(G)-1)}(G)=alpha(G)$. These bounds rely on the conic approximations $mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $ext{COP}_n$. A difficulty in the convergence analysis of $varthet{a}^{(r)}$ is the bad behaviour of the cones $mathcal{K}_n^{(r)}$ under adding a zero row/column: when applied to a matrix not in $mathcal{K}_n^{(0)}$ this gives a matrix not in any ${mathcalK}_{n+1}^{(r)}$, thereby showing strict inclusion $$ for $nge6$. We investigate the graphs with $varthet{a}^{(r)}(G)=alpha(G)$ for $r=0,1$: we algorithmically reduce testing exactness of $varthet{a}^{(0)}$ to acritical graphs, we characterize critical graphs with $varthet{a}^{(0)}$ exact, and we exhibit graphs for which exactness of $varthet{a}^{(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.

Full work available at URL: https://arxiv.org/abs/2109.12876

Recommendations

• Approximation of the stability number of a graph via copositive programming
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
• Copositive programming motivated bounds on the stability and the chromatic numbers
• On the accuracy of uniform polyhedral approximations of the copositive cone

zbMATH Keywords

polynomial optimizationsemidefinite programmingcopositive matrixstable set problemsum-of-squares polynomial\(\alpha\)-critical graphShor relaxation

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Semidefinite programming (90C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Sums of squares and representations by other particular quadratic forms (11E25) Polynomial optimization (90C23)

Cited In (2)

• A random copositive matrix is completely positive with positive probability
• Sum-of-squares certificates for copositivity via test states

This page was built for publication: Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199282)