# Maximum-k-cut

### Introduction

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.

### Problem formulation

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.

### Example

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.

### Complexity

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.

### Applications

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.