In this article we explain the task of determining maximum--cuts. A branch-and-cut algorithm for its solution can be used for determining exact ground states of Potts glasses.
In the maximum--cut problem, we are given a graph with edge weights for all edges . The task is to partition the nodes of the graph into at most sets so that the sum of the weights of the edges having endpoints in different sets is maximum. The latter edges are called cut edges. In the case , the maximum-2-cut problem is also referred to as max-cut.
In the example picture, the red edges are those in the cut. The set of nodes is partitioned into the black, green and orange nodes.
The maximum-k-cut problem is NP-hard. In [Ghaddar et al. (2007)] we determine optimum solutions using branch-and-cut based on positive semidefinite optimization.
One reason for the interest in the max-k-cut problem is that ground states of the Potts model can be computed by calculating maximum--cuts. There are further applications e.g. in telecommunication.