16. Semidefinite Relaxations for Max-Cut
Monique Laurent · Society for Industrial and Applied Mathematics eBooks · 2004
We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lovász and Schrijver and of Lasserre. We show that the tightest relaxation is obtained when applying the Lasserre construction to the node formulation of the max-cut problem. This relaxation Qt(G) can be defined as the projection on the edge subspace of the set ℱt (n), which consists of the matrices indexed by all subsets of {1, …, n} of cardinality ≤ t + 1 with the same parity as t + 1 and having the property that their (I, J)th entry depends only on the symmetric difference of the sets I and J. The set ℱ0(n) is the basic semidefinite relaxation of max-cut consisting of the semidefinite matrices of order n with an all ones diagonal, while ℱn−2(n) is the (2n−1)-dimensional simplex with the cut matrices as vertices. We show the following geometric properties. Let Y ∈ ℱt(n) and let X be its principal submatrix indexed by the first n rows and columns; if rank X ≤ t + 1, then Y can be written as a convex combination of at most 2t cut matrices; this extends a result of Anjos and Wolkowicz for the case t = 1. Any 2t+1 cut matrices form a face of ℱt(n) for t = 0, 1, n − 2. The class ℒt of the graphs G for which Qt(G) is equal to the cut polytope of G is shown to be closed under taking minors. The graph K7 is a forbidden minor for membership in ℒ2, while K3 and K5 are the only minimal forbidden minors for the classes ℒ0 and ℒ1, respectively.