Low degree sum-of-squares bounds for the stability number: a copositive approach

2025/09/05 by Vargas, Luis Felipe, Vera, Juan C., Dickinson, Peter J. C.
#Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2509.04949

Abstract

The stability number of a graph G, denoted as α(G), is the maximum size of an independent (stable) set in G. Semidefinite programming (SDP) methods, which originated from Lovász's theta number and expanded through lift-and-project hierarchies as well as sums of squares (SOS) relaxations, provide powerful tools for approximating α(G). We build upon the copositive formulation of α(G) and introduce a novel SDP-based hierarchy of inner approximations to the copositive cone COP_n, which is derived from structured SOS representations. This hierarchy preserves essential structural properties that are missing in existing approaches, offers an SDP feasibility formulation at each level despite its non-convexity, and converges finitely to α(G). Our results include examples of graph families that require at least α(G) - 1 levels for related hierarchies, indicating the tightness of the de Klerk-Pasechnik conjecture. Notably, on those graph families, our hierarchy achieves α(G) in a single step.

Citations

• Computational complexity of sum-of-squares bounds for copositive programs
• Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
• Exactness of Parrilo's conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

Related

• Computational complexity of sum-of-squares bounds for copositive programs
• Copositive matrices, sums of squares and the stability number of a graph
• Positive semidefinite approximations to the cone of copositive kernels
• Sum-of-squares certificates for copositivity via test states
• Application of the Lovász-Schrijver Lift-and-Project Operator to Compact Stable Set Integer Programs