Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914769120788480 |
|---|---|
| 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}_+$. In particular, we focus on a search for relatively small graphs with high $\text{LS}_+$-rank (i.e., the least number of iterations of the $\text{LS}_+$ operator on the fractional stable set polytope to compute the stable set polytope). We provide families of graphs whose $\text{LS}_+$-rank is asymptotically a linear function of its number of vertices, which is the best possible up to improvements in the constant factor. This improves upon the previous best result in this direction from 1999, which yielded graphs whose $\text{LS}_+$-rank only grew with the square root of the number of vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_08971 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator Au, Yu Hin Tunçel, Levent Optimization and Control Discrete Mathematics Combinatorics 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}_+$. In particular, we focus on a search for relatively small graphs with high $\text{LS}_+$-rank (i.e., the least number of iterations of the $\text{LS}_+$ operator on the fractional stable set polytope to compute the stable set polytope). We provide families of graphs whose $\text{LS}_+$-rank is asymptotically a linear function of its number of vertices, which is the best possible up to improvements in the constant factor. This improves upon the previous best result in this direction from 1999, which yielded graphs whose $\text{LS}_+$-rank only grew with the square root of the number of vertices. |
| title | Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator |
| topic | Optimization and Control Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2303.08971 |