The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918201785319424 |
|---|---|
| author | Gaar, Elisabeth Pucher, Dunja |
| author_facet | Gaar, Elisabeth Pucher, Dunja |
| contents | The stability number of a graph, defined as the cardinality of the largest set of pairwise non-adjacent vertices, is NP-hard to compute. The exact subgraph hierarchy (ESH) provides a sequence of increasingly tighter upper bounds on the stability number, 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 paper, 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 threshold 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 vertex-transitive ESH produces superior bounds compared to the ESH for Paley graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12958 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs Gaar, Elisabeth Pucher, Dunja Optimization and Control Discrete Mathematics 90C27, 90C22 The stability number of a graph, defined as the cardinality of the largest set of pairwise non-adjacent vertices, is NP-hard to compute. The exact subgraph hierarchy (ESH) provides a sequence of increasingly tighter upper bounds on the stability number, 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 paper, 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 threshold 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 vertex-transitive ESH produces superior bounds compared to the ESH for Paley graphs. |
| title | The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs |
| topic | Optimization and Control Discrete Mathematics 90C27, 90C22 |
| url | https://arxiv.org/abs/2412.12958 |