Cut polytope

From Cophy
Jump to: navigation, search

Contents

Introduction

This article introduces the polytope of cuts in a graph. Understanding its geometry is not only interesting from a theoretical point of view, but also necessary in order to be able to design an effective branch-and-cut algorithm for the max-cut problem. The latter can be used for determining exact ground states of Ising spin glasses, cf. the article about the computation of exact ground states of Ising spin glasses.

Definitions

The cut polytope is the convex hull of the incidence vectors of cuts in a graph. An explanation is given in the following.
Let δ(W) be the cut associated with node set W ⊆ V of a graph G = (V,E). With each cut, we can associate a so-called incidence vector of dimension | E | that contains an entry for each edge in G. In case edge e is in the cut, the corresponding entry is 1, otherwise it is 0. In formulas, let the incidence vector \scriptstyle\chi^{\delta(W)}\ \in\ \mathbb{R}^m for a cut δ(W) be defined by

\chi_e^{\delta(W)} =
\begin{cases}
1 & if\ e\ \in\ \delta(W), \\
0 & otherwise.
\end{cases}

Let us associate with each of the 2^{|V|-1} many cuts in G their corresponding incidence vectors. The latter are 0-1 vectors living in | E | -dimensional space. Taking the convex hull of all incidence vectors of cuts in G, we get the cut polytope PC(G):

P_C(G) = conv\{\chi^{\delta(W)}|\ \delta(W)\ is\ a\ cut\ in\ G\}\,\!.

Examples

Example (cut polytope for a graph consisting of a triangle)

The smallest interesting example for a cut polytope can be found for a graph that is a cycle of length three (a triangle), see Figure 1.

Cut Polytope figure1.jpg

For the triangle, we have four different cuts. Let us order the coordinates as (x12,x23,x13), where e.g., xij refers to the edge between node i and j.
The set of characteristic cut vectors for the triangle in Figure 1 is

\Bigg\{\begin{pmatrix}0 \\0 \\0 \end{pmatrix},\begin{pmatrix}0 \\1 \\1 \end{pmatrix},\begin{pmatrix}1 \\0 \\1 \end{pmatrix},\begin{pmatrix}1 \\1 \\0 \end{pmatrix}\Bigg\}.

In Figure 2 we show the cut polytope for the graph of Figure 1 PC(K3).

Figure 2

Understanding the geometry of the cut polytope in higher dimensions is essential for the design of an effective branch-and-cut algorithm for max-cut.

Personal tools