In this article we explain the task of determining maximum-k-cuts. A branch-and-cut algorithm for its solution can be used for determining exact ground states of Potts glasses.
In the maximum-k-cut problem, we are given a graph G = (V,E) with edge weights for all edges e∈E. The task is to partition the nodes of the graph into at most k 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 k = 2, 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-k-cuts. There are further applications e.g. in telecommunication.