531. Paley graphs, stable sets and the exact subgraph hierarchy: Bad and good news
Invited abstract in session MC-6: Nonsmooth optimization: from continuous to discrete Part II, stream Nonsmooth and nonconvex optimization.
Monday, 14:00-16:00Room: B100/7013
Authors (first author is the speaker)
| 1. | Elisabeth Gaar
|
| University of Augsburg | |
| 2. | Dunja Pucher
|
| Department of Mathematics, University of Klagenfurt |
Abstract
To determine the stability number of a graph, defined as the cardinality of the largest set of pairwise non-adjacent vertices, is a fundamental NP-hard discrete optimization problem. The exact subgraph hierarchy (ESH) provides a sequence of increasingly tighter upper bounds on the stability number based on non-smooth optimization, starting with the Lovász theta function at the first level and including all exact subgraph constraints of subgraphs of order k into the semidefinite program to compute the Lovász theta function at level k.
In this talk, we investigate the ESH for Paley graphs, a class of strongly regular, vertex-transitive graphs. We show that for Paley graphs, the bounds obtained from the ESH remain the Lovász theta function up to a certain level, i.e., the bounds of the ESH do not improve up to a certain level.
To overcome this limitation, we introduce the vertex-transitive ESH for the stable set problem for vertex-transitive graphs such as Paley graphs. We prove that this new hierarchy provides upper bounds on the stability number of vertex-transitive graphs that are at least as tight as those obtained from the ESH. Additionally, our computational experiments reveal that the local ESH produces superior bounds compared to the ESH for Paley graphs.
Keywords
- Conic and semidefinite optimization
- Non-smooth optimization
Status: accepted
Back to the list of papers