A Computational Search for Minimal Obstruction Graphs for the Lovász–Schrijver SDP Hierarchy
\(\)
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. In particular, we focus on searching for \( \ell \)-minimal graphs, which are graphs on $3\ell$ vertices whose stable set polytope has rank \( \ell \) with respect to \( \text{LS}_+ \). These are the graphs which are the most challenging for the \( \text{LS}_+ \) operator according to one of the main complexity measures (smallest graphs with largest \( \text{LS}_+ \)-rank). We introduce the notion of \( \text{LS}_+ \), certificate packages, which is a framework that allows for efficient and reliable verification of membership of points in \( \text{LS}_+ \)-relaxations. Using this framework, we present numerical certificates which (combined with other results) show that there are at least \( 49 \) \(3\)-minimal graphs, as well as over \(4000\) \(4\)-minimal graphs. This marks a significant leap from the \(14\) \(3\)-minimal and \(588\) \(4\)-minimal graphs known before this work, with many of the newly-discovered graphs containing novel structures which helps enrich and recalibrate our understanding of \( \ell \)-minimal graphs. Some of this computational work leads to interesting conjectures. We also find all of the smallest vertex-transitive graphs with \( \text{LS}_+ \)-rank \( \ell \) for every \( \ell \leq 4\).