A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy

Yu Hin Au, Levent Tunçel

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 fo…