762. A low-degree sum-of-squares bound for the stable set problem: A copositive approach
Invited abstract in session MA-49: Sums-of-squares optimization, stream Conic and polynomial optimization.
Monday, 8:30-10:00Room: Parkinson B10
Authors (first author is the speaker)
| 1. | Luis Felipe Vargas
|
| SUPSI |
Abstract
The stability number of a graph \(G\), denoted by $\alpha(G)$, represents the maximum size of a stable (or independent) set in \(G\). Building on the theta number introduced by Lovász, several semidefinite programming (SDP) approaches have been proposed to approximate $\alpha(G)$, typically involving lift-and-project methods or sums of squares relaxations.
In this talk, we introduce a novel hierarchy of approximations based on structured sums of squares representations. We prove that this hierarchy converges to $\alpha(G)$ and provide quantitative bounds on its convergence rate. Remarkably, we show that for several graph instances known to be hard for existing SDP-based methods, our hierarchy converges to $\alpha(G)$ in just one step. We conclude with a discussion on the computability of and complexity implications of our approach.
This is based on my joint work with Juan Vera and Peter Dickinson.
Keywords
- Combinatorial Optimization
- Programming, Semidefinite
- Complexity and Approximation
Status: accepted
Back to the list of papers