Geometry of Semidefinite Max-Cut Relaxations via Ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice. Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let ${\cal F}_n$ denote the feasible set of SDP2 for the complete graph with $n$ nodes, let $F_n$ denote the appropriately defined projection of ${\cal F}_n$ into $\Sn$, the space of real symmetric $n \times n$ matrices, and let $C_n$ denote the cut polytope in $\Sn$. Further let $Y \in {\cal F}_n$ be the matrix variable of the SDP2 relaxation and $X \in F_n$ be its projection. Then for the complete graph on 3 nodes, $F_3 = C_3$ holds. We prove that the rank of the matrix variable $Y \in {\cal F}_3$ of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix $X$ lies. This shows explicitly the connection between the rank of the variable $Y$ of the second lifting and the possible locations of the projected matrix $X$ within $C_3$. The results we prove for $n=3$ cast further light on how SDP2 captures all the structure of $C_3$, and furthermore they are stepping stones for studying the general case $n \geq 4$. For this case, we show that the characterization of the vertices of the cut polytope via $\rank Y = 1$ extends to all $n \geq 4$. More interestingly, we show that the characterization of the one-dimensional faces via $\rank Y = 2$ also holds for $n \geq 4$. Furthermore, we prove that if $\rank Y = 2$ for $n \geq 3$, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where $X$ lies.


Journal of Combinatorial Optimization, Vol. 6 (3), 2002, 237-270.