# Computing minimum cuts

## Contents

### Introduction

The minimum cut problem and the maximum **flow** problem, have many applications and arise in a wide variety of problems,
some of which are surveyed by [Picard and Queyranne (1982)].
For example the minimum cut problem occurs as a series of subproblems in computing optimum solutions for the partition function for the Potts model with many states.
We will briefly introduce how to solve the minimum cut problem with network flow techniques.

### Definitions

Let be a directed graph with a source and a sink , . Let be the number of nodes and the number of edges. Let be a "capacity function" that assigns nonnegative weights to the edges of the graph and denotes how much "flow" can be sent over an edge.

A set is called *s-t cut* if and . The value of an s-t cut is the capacity of all outgoing edges

- .

A s-t cut is called minimum if it has the smallest value among all s-t cuts.

As the value of a maximum s-t flow equals the value of the minimum s-t cut (max flow / min cut theorem of Ford/Fulkerson), we can use flow techniques to compute s-t cuts. In the following we want to determine a minimum s-t cut by using the push-relabel algorithm. The push-relabel algorithm is used to compute a maximum s-t flow which directly yields a minimum s-t cut .

Thus, assume we computed a maximum flow . Then we can compute a valid labelling with

- for all nodes

Where and denote the minimum length of a directed path in the residual graph from to and , respectively. Then the following theorem holds.

### Theorem (maximum cardinality s-t cut)

The set

is a minimum s-t cut with maximum cardinality .

For a minimum s-t cut with minimum cardinality we can use the following theorem.

### Theorem (minimum cardinality s-t cut)

Let be a function with

- for all nodes

Then the following set

is a minimum cut with minimum cardinality .

### Example

We want to determine a maximum flow in the following graph. The edge labels denote the edge capacity and the current flow on this edge.

- Error creating thumbnail: File missing

Then the push-relabel algorithm computes a maximum flow f and a residual graph as follows:

**:**

- Error creating thumbnail: File missing

Red edges are used for sending flow from to .

**:**

- Error creating thumbnail: File missing

Note that no capacities or flow values are given in the figure showing the residual graph.

Then we obtain the following values and for the nodes .

Thus, and are minimum s-t cuts.

If we are not interested in the maximum s-t flow, but only in the minimum s-t cut of a given graph, we can modify the push-relabel algorithm as follows:

The basic operations in the push-relabel algorithm are performed on so-called active nodes. That is, we call a node active if and only if the "flow excess" (cf. the definition of a preflow) is positive and for the valid labelling. The modified algorithm terminates with a preflow , and the flow excess is the value of a maximum flow.

Furthermore, we can compute a minimum cut that contains all nodes for which in there exists no directed path to the sink , i.e., we can use the formulae (1) and (2).