# 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 *G* = (*V*,*E*) be a directed graph with a source *s* ∈*V* and a sink *t* ∈ *V*, *s* ≠ *t*. Let *n* = | *V* | be the number of nodes and *m* = | *E* | 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 *S* ⊆ *V* is called *s-t cut* if *s* ∈ *S* and *t* ∉ *S*. The value of an s-t cut *S* 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 *f* which directly yields a minimum s-t cut *S*.

Thus, assume we computed a maximum *s* − *t* flow *f*. Then we can compute a valid labelling with

- for all nodes

Where *d*_{f} (*v*,*s*) and *d*_{f} (*v*,*t*) denote the minimum length of a directed path in the residual graph *G*_{f} from *v* to *s* and *t*, respectively. Then
the following theorem holds.

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

The set

is a minimum s-t cut with maximum cardinality | *S* | .

For a minimum s-t cut *S*' with minimum cardinality | *S*' | 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 *s* − *t* cut with minimum cardinality | *S*' | .

### Example

We want to determine a maximum flow in the following graph.
The edge labels (*c*_{e},*f*_{e}) denote the edge capacity and the current flow on this edge.

Then the push-relabel algorithm computes a maximum flow f and a residual graph *G*_{f} as follows:

*f*:

Red edges are used for sending flow from *s* to *t*.

*G*_{f}:

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

Then we obtain the following values *d*(*v*) and *d*'(*v*) for the nodes *v* ∈ *V*.

Thus, *S* = {*s*, *a*, *b*, *d*} and *S*' = {*s*, *b*} 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 *v* ∈ *V* \{*s*, *t*} active if and only if the "flow excess" *e*_{f} (*v*) (cf. the definition of a preflow) is positive and *d*(*v*) < *n* for the valid labelling.
The modified algorithm terminates with a preflow *f*, and the flow excess *e*_{f} (*t*) is the value of a maximum flow.

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