Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

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}}_{+}$. In particular, we focus on a search for r…