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

• 成果类型: Article
• 署名作者: Laurent, Monique; Vargas, Luis Felipe
• 署名单位: Tilburg University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1290
• 发表日期: 2023
• 页码: 1017-1043
• 关键词: semidefinite; complexity; squares

摘要

De Klerk and Pasechnik introduced in 2002 semidefinite bounds theta((r))(G)(r >= 0) for the stability number alpha(G) of a graph G and conjectured their exactness at order r = alpha(G) - 1. These bounds rely on the conic approximations K-n((r)) 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-n((r)) 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 theta((0)) to a critical graphs, we characterize the critical graphs with theta((0)) exact, and we exhibit graphs for which exactness of theta((1)) is not preserved under adding an isolated node. This disproves a conjecture posed by Gvozdenovic and Laurent in 2007, which, if true, would have implied the above conjecture by de Klerk and Pasechnik.