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 … Read more