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 LS_+, with a particular focus on finding and characterizing the smallest graphs with a given LS_+-rank (the least number of iterations of the 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 LS_+-minimal graphs and study its properties. We also provide several new LS_+-minimal graphs, most notably the first known instances of 12-vertex graphs with LS_+-rank 4, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a 9-vertex graph with LS_+-rank 3 in 2006.

Article

Download

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