On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912135483752448 |
|---|---|
| author | Au, Yu Hin Tunçel, Levent |
| author_facet | Au, Yu Hin Tunçel, Levent |
| contents | We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász--Schrijver SDP operator $\text{LS}_+$, with a particular focus on finding and characterizing the smallest graphs with a given $\text{LS}_+$-rank (the needed number of iterations of the $\text{LS}_+$ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating $\text{LS}_+$-minimal graphs and study its properties. We also provide several new $\text{LS}_+$-minimal graphs, most notably the first known instances of $12$-vertex graphs with $\text{LS}_+$-rank $4$, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a $9$-vertex graph with $\text{LS}_+$-rank $3$ in 2006. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_01476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy Au, Yu Hin Tunçel, Levent Discrete Mathematics Combinatorics Optimization and Control We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász--Schrijver SDP operator $\text{LS}_+$, with a particular focus on finding and characterizing the smallest graphs with a given $\text{LS}_+$-rank (the needed number of iterations of the $\text{LS}_+$ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating $\text{LS}_+$-minimal graphs and study its properties. We also provide several new $\text{LS}_+$-minimal graphs, most notably the first known instances of $12$-vertex graphs with $\text{LS}_+$-rank $4$, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a $9$-vertex graph with $\text{LS}_+$-rank $3$ in 2006. |
| title | On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy |
| topic | Discrete Mathematics Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2401.01476 |