We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations suffice instead of the $m$ (number of edges) iterations required in general and, under some assumption, $n-\alpha(G)-3$ iterations suffice. The exact number of needed iterations is determined for small $n\le 7$ by a detailed analysis of the new relaxations. If positive semidefiniteness is added to the construction, then one finds in one iteration a relaxation of the cut polytope which is tighter than its basic semidefinite relaxation and than another one introduced recently by Anjos and Wolkowicz \cite{AW00}. We also show how the Lov\’asz-Schrijver relaxations for the stable set polytope of $G$ can be strenghtened using the corresponding relaxations for the cut polytope of the graph $G^\nabla$ obtained from $G$ by adding a node adjacent to all nodes of $G$.
Citation
SIAM Journal on Optimization, 12:345--375, 2001