# Maximum-k-cut

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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 $c_{ij}\ \in\ \mathbb{R}$ for all edges $e \in 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.