Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 26

The authors discuss about flow networks in this chapter. A flow network is a directed graph $ G = (V, E) $ in which every edge $(u,v) \in E$ has a nonnegative capacity $ c(u,v) $ associated with it. If $(u,v) \notin E $ then $ c(u,v) = 0 $. There are two distinguished vertices source $s$ and sink $t$. For every vertex $v$, there is a path $ s \leadsto v \leadsto t $. A flow in $G$ is defined as follows:

* Capacity constraint: For all $u,v \in V$, $ f(u,v) \le c(u,v) $.
* Skew symmetry: For all $u,v \in V$, $ f(u,v) = -f(v,u) $.
* Flow conservation: For all $u \in V - {s,t}$, we require $ \displaystyle\sum\limits_{v \in V} f(u,v) = 0 $.

The value of a flow $f$ is defined as $ |f| = \displaystyle\sum\limits_{v \in V} f(s, v) $. In the maximum flow problem, given a flow network $G$ with source $s$ and sink $t$, our aim is to find flow of maximum value.

The authors describe networks with multiple sources and sinks and provides a way to convert it to a single source single sink problem. The authors then prove some properties of flow.

The authors first define residual flow between a set of vertices $ u,v \in V $ as
$ c_f (u,v) = c(u,v) - f(u,v) $.
The residual network of $G$ introduced by $f$ is $G_f = (V,E_f) $ where $ E_f = { (u,v) \in V \times V : c_f(u,v) > 0} $. Each edge that is part of residual network is called residual edge and as per the definition has a positive residual flow. The author points out that the residual network $G_f$ is also a flow network with capacities given by $c_f$. The authors define augmenting path $p$ as a simple path in the residual network from $s$ to $t$ in the residual network $G_f$ such that each edge $(u,v)$ admits an additional positive flow from $u$ to $v$ without violating the capacity constraint on the edge.

The authors then prove some lemmas and theorems on the property of residual network which are as follows:

• Let $f$ be a flow in a flow network $G$ with source $s$ and sink $t$ and $(S,T)$ be a cut of $G$. Then the net flow across $(S,T)$ is $f(S,T) = |f|$.
• Max-flow min-cut theorem: If $f$ is a flow in a flow network $G=(V,E)$ with source $s$ and sink $t$, then the following conditions are equivalent:
  
  • $f$ is a maximum flow in $G$.
  • The residual network $G_f$ contains no augmenting paths.
  • $|f| = c(S,T)$ for some cut $(S,T)$ of $G$.

The authors then descibe Ford-Fulkerson algorithm for finding the maximum flow of a flow network. The authors also derive that the running time of the algorithm is $O(E |f*|)$ where $f*$ is the maximum flow found by the algorithm.

The authors then describe Edmonds-Karp algorithm and prove its running time to be $O(V \times E^2)$.

The authors then discuss the problem of maximum-bipartite-matching. A matching for a given undirected graph $G = (V,E)$ is a subset of edges $M \subset E$ such that for all vertices $v \in V$, at most one edge of $M$ is incident on $v$. A maximum matching is a matching with the maximum cardinality. The authors provide a way to transform a bipartite graph to a network flow graph and show how solution obtained by application of Ford-Fulkerson method to such graph is a solution to maximum matching problem.

The authors then discuss push-relabel algorithms which, unlike Ford-Fulkerson method, do not maintain the flow-conservation property throughout their execution. The authors also define the concept of excess flow and an overflowing vertex. The authors then describe the basic intuition behind push-relabel algorithm and define the two main operations PUSH and RELABEL for the algorithm.

The authors then prove many lemmas and theorems to prove the correctness of the push-relabel method and prove the running time of the algorithm to be $O(V^2 \times E)$.

The authors then discuss the relabel-to-front algorithm. The authors define the concept of admissible edge and admissible network. The authors then prove some lemmas proving properties of admissible network including that the admissible network is acyclic. The authors introduce the concept of neighbour-list for a vertex. The authors then describe operation DISCHARGE which uses neighbour-list as well as PUSH and RELABEL operations.

The authors then describe RELABEL-TO-FRONT algorithm and proves its running time to be $O(V^3)$.