Computing minimum cuts

From Cophy
Jump to: navigation, search

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 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 ⊆ 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

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 st  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 df (v,s) and df (v,t) denote the minimum length of a directed path in the residual graph Gf  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 st  cut with minimum cardinality | S' | .

Example

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

Example 1


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

f:

Computing minimum cuts example graph f.jpg

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

Gf:

Computing minimum cuts example graph Gf.jpg

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.

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 = {sabd} and S' = {sb} 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 \{st} active if and only if the "flow excess" ef (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 ef (t) is the value of a maximum flow.

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

Personal tools