Maximum-k-cut

From cophywiki
Jump to: navigation, search

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

3cut.jpg

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.