Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure

We study how the lift-and-project method introduced by Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] 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 K5 -minor. Therefore, for a graph G with n≥ 4 nodes with stability number α(G), n-4 iterations suffice instead of the m (number of edges) iterations required in general and, under some assumption, n-α(G)-3 iterations suffice. The exact number of needed iterations is determined for small n≤ 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 [Discrete Appl. Math., to appear]. We also show how the Lovász--Schrijver relaxations for the stable set polytope of G can be strengthened using the corresponding relaxations for the cut polytope of the graph G^∇ obtained from G by adding a node adjacent to all nodes of G.