On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy

Yu Hin Au, Levent Tunçel

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász--Schrijver SDP operator ${\text{LS}}_{+}$, with a particular focus on finding and c…