Max-flow Problem

Given a flow network, a natural goal is to arrange the traffic so as to make as efficient use as possible of the available capacity. Thus, the problem is: given a flow network, find a flow of maximum possible value.

As we think about designing an algorithm for this purpose, it is useful to consider how the structure of the flow network places upper bounds on the maximum value of an s-t flow. Suppose we divide the nodes of the graph into two sets, $S$ and $T$, so that $s \in S$ and $t \in T$. Then, any flow that goes from $s$ to $t$ must cross from $S$ into $T$ at some point, and hence will use some of the edge capacity from $S$ to $T$.

Definition 2.2   Cut. The set of edges ( $\{u_i, v_j\}$) which partitions the network into sets $S$, $T$, is called cut-set of this graph.

This suggests that each such “cut” of the graph puts bound on the maximum possible flow value. The maximum flow algorithm, we are going to discuss, will have maximum flow limited to the minimum capacity of such divisions, called minimum-cut. Hence, we would require to find minimum capacity in a flow network for finding the maximum flow.

A flow function $f : (u, v) \mapsto \mathbb{R}$ maps edges to real numbers. For an edge $e = (u, v)$, $f(u, v)$ refers to the flow on edge $e$, which is also called the net flow from vertex $u$ to vertex $v$. This notation is extended to sets of vertices as follows: If $X$ and $Y$ are sets of vertices then $f(X, Y)$ can be defined as,

$$\sum_{x \in X}\sum_{y \in Y} f(x, y).$$ (2.4)

First, the notation of cuts is defined, and the max-flow min-cut theorem is introduced. Then, residual networks, layered networks, and the concept of blocking flows are introduced. Finally, an efficient algorithm for finding a blocking flow is described.

An s-t cut of the graph is partitioning of the vertex $V$ into two sets $S$ and $T = V - S$ such that $s \in S$ and $t \in T$. If $f$ is a flow, then the net flow across the cut is defined as $f(S, T)$. The capacity of the cut is similarly defined as,

$$c(S, T) = \sum_{x \in X} \sum_{y \in Y} c(x , y).$$ (2.5)

The net flow across a cut may include negative net flow between vertices, but the capacity of the cut includes only negative values, i.e., only the capacity of edges from $S$ to $T$.

Using the flow conservation principle, it can be shown that the net flow across an s-t cut is exactly the flow value $\vert f\vert$. By the capacity constraint, the flow across the cut cannot exceed the capacity of the cut. Thus the value of maximum flow is no greater than the capacity of a minimum s-t cut. The well-known max-flow min-cut theorem proves that the two numbers are actually equal. In other words, if $f^\ast$ is a maximum flow, then there is some cut $(X, \bar{X})$ such that $\vert f^\ast\vert$ = $c(X, \bar{X})$.

Definition 2.3   Residual Capacity. The residual capacity of a flow $f$ is defined to be a function on vertex pair $(u, v)$ given by $c^\prime(u, v) = c(u,v) - f(u, v)$. The residual capacity of an edge $(u, v)$, expressed as $c^\prime(u, v)$, is the number of additional units of flow that can be pushed from $u$ to $v$ without violating the capacity constraints.

Definition 2.4   Saturated Edge. And edge $(u, v)$ is saturated if $c(u, v) = f(u, v)$, that is, if the residual capacity, $c^\prime(u, v)$, is zero.

Definition 2.5   Residual Graph. The residual graph $G_R(f)$ for a flow $f$ is the graph with vertex set $V$, source and sink $s$ and $t$, respectively, and those edges $(u, v)$ for which $c^\prime(u, v) > 0$. These edges are marked with $c^\prime(u, v)$.

Definition 2.6   Augmented Path. An augmented path for $f$ is a path in $G_R(f)$.

Definition 2.7   Residual Capacity of a Path. The residual capacity of path $P$, denoted by $c^\prime(P)$, is the minimum value of $c^\prime(u, v)$ over all edges $(u, v)$ in the path $P$. The flow can be increased by $c^\prime(P)$, by increasing the flow on each edge of $P$ by this amount.

Whenever $f(u, v)$ is changed, $f(v, u)$ is also correspondingly changed to maintain the skew symmetry.

Most flow algorithms are based on augmenting the flow in stages. In each stage, a residual graph $G_R(f)$ with respect to the current flow function $f$ is constructed and an augmenting path in $G_R(f)$ is found to increase the value of the flow. Flow is increased along with this path until an edge in this path is saturated. The algorithm iteratively keeps increasing the flow until there are no augmenting paths in $G_R(f)$, and return the final flow $f$ as output.

Lemma 2.8   Let $f$ be any flow and $f^\ast$ a maximum flow in $G$, and let $G_R(f)$ be the residual flow graph for $f$. The value of a maximum flow in $G_R(f)$ is $\vert f^\ast\vert-\vert f\vert$.

Proof. Let $f^\prime$ be any flow in $G_R(f)$. Define $f + f^\prime$ to be the flow defined by the flow function $f(u, v) + f^\prime(u, v)$ for each edge $(u, v)$. Observe that $f + f^\prime$ is a feasible flow in $G$ of value $\vert f\vert + \vert f^\prime\vert$. Since, $f^\ast$ is the maximum flow possible in $G$, $\vert f^\prime\vert \leq \vert f^\ast\vert - \vert f\vert$. Similarly, define $f^\ast -f$ to be a flow in $G_R(f)$ defined by $f^\ast(u, v) - f(u, v)$ in each edge $(u, v)$, and this is a feasible flow in $G_R(f)$ of value $\vert f^\ast\vert-\vert f\vert$, and it is a maximum flow in $G_R(f)$. $\Box$.

Definition 2.9   Blocking Flow. A flow $f$ is blocking flow if every path in $G$ from $s$ to $t$ contains a saturated edge.

Blocking flows are also known as maximal flows. It is important to note that a blocking flow is not necessarily maximum flow. There may be augmented paths that increase the flow on some edge and decrease the flow on other edges (by increasing the flow in the reverse direction).

The maximum flow algorithm proposed by Dinitz starts with zero flow, and iteratively increases the flow by augmenting it with a blocking flow in $G_R(f)$ until the vertex $t$ is not reachable from $s$ in $G_R(f)$. At each step the present flow is replaced by the sum of the present flow and blocking flow. The algorithm terminates in $\vert V\vert-1$ iterations since in each iteration the shortest distance from $s$ to $t$ in the residual graph increases. The shortest path from $s$ to $t$ is at most $\vert V\vert-1$, and this gives upper bound of the number of iterations of the algorithm.