A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
For researchers studying lift-and-project relaxations and the stable set polytope, this work provides a more reliable verification method and significantly expands the known set of minimal graphs, revealing new structural insights.
The authors introduce LS+ certificate packages for certifying membership in LS+ relaxations using integer arithmetic, and use them to search for minimal obstruction graphs. They find at least 49 non-isomorphic 3-minimal graphs (up from 14) and at least 4,107 non-isomorphic 4-minimal graphs (up from 588).
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$.