A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913033972875264 |
|---|---|
| author | Au, Yu Hin Tunçel, Levent |
| author_facet | Au, Yu Hin Tunçel, Levent |
| contents | We study the lift-and-project relaxations of the stable set polytope of graphs generated by $\text{LS}_+$, the SDP lift-and-project operator devised by Lovász and Schrijver. Our focus is on $\ell$-minimal graphs: graphs on $3\ell$ vertices with $\text{LS}_+$-rank $\ell$, i.e., the smallest graphs realizing rank $\ell$. This manuscript makes two complementary contributions. First, we introduce $\text{LS}_+$ certificate packages, a modular framework for certifying membership in $\text{LS}_+$-relaxations using only integer arithmetic and simple, concise calculations, thereby making numerical lower-bound proofs more transparent, reliable, and easier to verify. Second, we apply this framework to a computational search for extremal graphs. We prove that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs, improving the previously known counts of 14 and 588, respectively. Beyond the increase in counts, the new examples sharpen the emerging structural picture: stretched cliques remain central but are not exhaustive, clique number is informative but not decisive, and some extremal graphs exhibit previously unseen graph minor and edge density behaviour. We also determine the smallest vertex-transitive graphs of $\text{LS}_+$-rank $\ell$ for every $\ell \leq 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24735 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy Au, Yu Hin Tunçel, Levent Combinatorics Discrete Mathematics Optimization and Control 90C22, 90C27 We study the lift-and-project relaxations of the stable set polytope of graphs generated by $\text{LS}_+$, the SDP lift-and-project operator devised by Lovász and Schrijver. Our focus is on $\ell$-minimal graphs: graphs on $3\ell$ vertices with $\text{LS}_+$-rank $\ell$, i.e., the smallest graphs realizing rank $\ell$. This manuscript makes two complementary contributions. First, we introduce $\text{LS}_+$ certificate packages, a modular framework for certifying membership in $\text{LS}_+$-relaxations using only integer arithmetic and simple, concise calculations, thereby making numerical lower-bound proofs more transparent, reliable, and easier to verify. Second, we apply this framework to a computational search for extremal graphs. We prove that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs, improving the previously known counts of 14 and 588, respectively. Beyond the increase in counts, the new examples sharpen the emerging structural picture: stretched cliques remain central but are not exhaustive, clique number is informative but not decisive, and some extremal graphs exhibit previously unseen graph minor and edge density behaviour. We also determine the smallest vertex-transitive graphs of $\text{LS}_+$-rank $\ell$ for every $\ell \leq 4$. |
| title | A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy |
| topic | Combinatorics Discrete Mathematics Optimization and Control 90C22, 90C27 |
| url | https://arxiv.org/abs/2505.24735 |