Semidefinite relaxations for sparse Max-Cut problems

Angelika Wiegele

We investigate semidefinite relaxations of the Max-Cut problem, which are
formulated in terms of the edges of the graph, thereby exploiting the
(potential) sparsity of the problem. We show how this is related to higher
order liftings of Anjos and Wolkowicz and Lasserre. Contrary to the basic
semidefinite relaxation, which is based on the nodes of the graph, the
present formulation leads to a model which is significantly more difficult
to solve.

We present preliminary computational results using the spectral bundle
method where we make partial use of second-order information. These
results indicate that this model is manageable for sparse graphs on a few
hundred nodes and yields very tight bounds.
(joint work with F. Rendl)