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

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 characterizing the smallest graphs with a given ${\text{LS}}_{+}$-rank (the needed number of iterations of the ${\text{LS}}_{+}$ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating ${\text{LS}}_{+}$-minimal graphs and study its properties. We also provide several new ${\text{LS}}_{+}$-minimal graphs, most notably the first known instances of $12$-vertex graphs with ${\text{LS}}_{+}$-rank $4$, which provides the first advance in this direction since Escalante, Montelar, and Nasini’s discovery of a $9$-vertex graph with ${\text{LS}}_{+}$-rank $3$ in 2006.