Computing minimum cuts

From cophywiki
Jump to: navigation, search


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.


Let G = (V,E) be a directed graph with a source  s\ \in V\ and a sink t\ \in\ V, \ s\ \ne\ t. Let n = |V| be the number of nodes and m = |E| the number of edges. Let c:\ E\ \rightarrow\ \mathbb{R}_+ 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\ \subseteq\ V is called s-t cut if s\ \in\ S and t\ \notin\ S. The value of an s-t cut S is the capacity of all outgoing edges

c(\delta^+(S)) = \sum\limits_{(v,w)\ \in\ E:\ v\ \in\ S,\ w\ \notin\ S} c(v,w).

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 d:\ V\ \rightarrow\ \mathbb{N}\ \cup\ \{0,\infty\} with

d(v) = min\{d_f\ (v,s) + n, d_f\ (v,t)\}\,\! for all nodes v\ \in\ V.\qquad (1)\,\!

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

S = \{v\ \in\ V:\ d(v)\ \ge\ n\}\qquad (2)\,\!

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 d':\ V\ \rightarrow\ \mathbb{N}\ \cup\ \{0,\infty\} be a function with

d '(v) = min\{d_f\ (s,v), d_f\ (t,v) + n\}\,\! for all nodes v\ \in\ V.\qquad (3)\,\!

Then the following set

S' = \{v\ \in\ V:\ d(v)\ <\ n\}\qquad (4)\,\!

is a minimum  s-t\ cut with minimum cardinality |S'|.


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.

Error creating thumbnail: File missing

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


Error creating thumbnail: File missing

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


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 d(v) and d'(v) for the nodes v\ \in\ V.

d(s) = 6,\ d(a) = d(b) = d(d) = 7,\ d(c) = 1,\ d(t) = 0,\,\!
d'(s) = 0,\ d'(a) = 7,\ d'(b) = 1,\ d'(c) = 7,\ d'(d) = 8,\ d'(t) = 6.\,\!

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\ \in\ V\,\setminus \{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).