Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
share
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 a search for relatively small graphs with high LS_+-rank (the least number of iterations of the LS_+ operator on the fractional stable set polytope to compute the stable set polytope). We provide families of graphs whose LS_+-rank is asymptotically a linear function of its number of vertices, which is the best possible up to improvements in the constant factor (previous best result in this direction, from 1999, yielded graphs whose LS_+-rank only grew with the square root of the number of vertices). We also provide several new LS_+-minimal graphs, most notably a 12-vertex graph with LS_+-rank 4, and study the properties of a vertex-stretching operation that appears to be promising in generating LS_+-minimal graphs.
READ FULL TEXT