Cut polytope

From cophywiki
Jump to: navigation, search

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 \delta(W) be the cut associated with node set W\ \subseteq\ 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 \delta(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 P_C(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.

Error creating thumbnail: File missing

For the triangle, we have four different cuts. Let us order the coordinates as (x_{12},x_{23},x_{13}), where e.g., x_{ij} 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 P_C(K_3).

Error creating thumbnail: File missing

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.