# Maximum-k-cut

## Contents |

### Introduction

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.

### Problem formulation

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.

### 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-*k*-cuts. There are further applications e.g. in telecommunication.