# 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 eE. 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.