Geometry of Semidefinite Max-Cut Relaxations via Ranks
Miguel F. Anjos and Henry Wolkowicz
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.
Research Report CORR 2001-39, Department of Combinatorics & Optimization,
University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Contact: [email protected]