1. Flow Network

Graphs are often used to model transportation networks such as traffic control or airline scheduling, and this particular kind of graph are always called Flow Networks. Thus, the formal definition of flow network we are discussing here is a directed graph $G=(V,E)$ with following features.

• Each edge has a capacity of flow which is labeled as a nonnegative integer $c_e, e\in{E}$ and $c_e\geq{0}$
• A single source node $s\in{V}$
• A single sink node $t\in{V}$

2. Max-flow Min-cut Problem

Before getting into this problem, we first need to understand what is flow and what is cut.

2.1 Flow and Max-flow

Flow: A flow from $s$ to $t$ is a function $f$ that maps each edge $e$ to a nonnegative real number; the value assigned on each edge $f(e)$ represents the amount of flow carried by edge $e$. A flow also must satisfy the following two conditions.

• For each $e\in{E}$, we have $0\leq{f(e)}\leq{c_e}$. [Capacity]
• For each node $v$ other than $s$ and $t$, we have $\sum\limits_{e\ into\ v} f(e) = \sum\limits_{e\ out\ of\ v} f(e)$. [Conservation]

The value of a flow $f$, denote $v(f)$, is defined to be the amount of flow generated at the source. $v(f)=\sum\limits_{e\ out\ of\ s} f(e)$.

Therefore, it is obvious that the max-flow problem refers to find a flow that maximize the value $v(f)$.

Note that like the "conservation of energy", a flow never disappear, which means the amount of flow received by the sink $t$ should exactly equals to the amount of flow generated at the source $s$.

2.2 Cut and Min-cut

Cut A cut of a flow network is a partition $(A,B)$ of the vertices with $s\in{A}$ and $t\in{B}$.

The value or usually called the capacity of a cut is the sum of the capacities of the edges from $A$ to $B$. $cap(A,B)=\sum\limits_{e\ out\ of\ A} c(e)$.

Therefore, it is clear that the min-cut problem wants to find a cut that minimize the capacity $cap(A,B)$.

Note to be careful that do not be confused by the name cut. You don't actually need to find a line which divide the graph into two parts. In fact you can pick nodes into $A$ or $B$ arbitrary as long as $s\in{A}$ and $t\in{B}$.

3. Max-flow Min-cut Theorem

You might already sense something special in these two problems, and it turns out that $v(f) = cap(A,B)$ (i.e. The value of max flow equals the capacity of min cut).

In order to prove it, we need two lemmas.

Lemma 1. Let $f$ be any $s-t$ flow and let $(A,B)$ be any $s-t$ cut. Then, the net flow across $(A,B)$ equals the value of $f$. $\sum\limits_{e\ out\ of\ A} f(e) - \sum\limits_{e\ into\ A} f(e) = v(f)$.

Proof. By definition we have $v(f)=f_{out}(s)$ and $0=f_{in}(s)$. Then we could rewrite the left hand side of equation above to $\sum\limits_{v\in{A}} (f_{out}(v)-f_{in}(v))$. Since all nodes $v$ in $A$ except $s$ are internal nodes (i.e. $f_{out}(v)-f_{in}(v) = 0$), so the only thing left is $f_{out}(s) - f_{in}(s) = v(f)$.

Lemma 2. Let $f$ be any $s-t$ flow and $(A,B)$ be any $s-t$ cut. Then $v(f)\leq{cap(A,B)}$.

Proof. Since $v(f) = \sum\limits_{e\ out\ of\ A} f(e) - \sum\limits_{e\ into\ A} f(e)$ and flow values are nonnegative, then $v(f)\leq{\sum\limits_{e\ out\ of\ A} f(e)}$. Then $v(f)\leq{\sum\limits_{e\ out\ of\ A} c(e)}=cap(A,B)$.

Therefore, from Lemma 1 we get Lemma 2 and from Lemma 2 we can obtain $v(f)=min(cap(A,B))$.

4. Ford-Fulkerson Algorithm

Ford-Fulkerson algorithm is a famous polynomial time algorithm to solve max-flow min-cut problem. The core of this algorithm is very simple (informally): Start with $f(e)=0$ for all edge $e\in{E}$. In each iteration compute a residual graph then find an augmenting path $P$ in the graph and augment flow along path $P$, repeat until no augmenting path can be found.

Thus the key problem we need to solve now is how to compute residual graph and augmenting path.

4.1 Residual Graph

Given a network $G$ and a flow $f$ on $G$, the residual graph $G_f$ of $G$ is defined as follows:

• The node set of $G_f$ is the same as that of $G$.
• For each edge $e=(u,v)$ of $G$ on which $f(e)<{c_e}$, we include edge $e=(u,v)$ in $G_f$, with capacity of $c_e-f(e)$. [Forward edges]
• For each edge $e=(u,v)$ of $G$ on which $f(e)>{0}$, we include edge $e'=(v,u)$ in $G_f$, with capacity of $f(e)$. [Backward edges]

4.2 Augmenting Path

An augmenting path $P$ is a simple $s-t$ path in $G_f$, that is $P$ does not visit any node more than once. In addition, we define a bottlenect value $b$ to be the minimum residual capacity of any edge on $P$, with respect to the flow $f$. Then we could yield $f'$ from $f$ by:

• For each edge $(u,v)\in{P}$:
• If $e=(u,v)$ is a forward edge, then increase $f(e)$ in $G$ by $b$.
• Else $e=(u,v)$ is a backward edge, then decrease $f(e)$ in $G$ by $b$.

4.3 Result of Max-flow Min-cut

In terms of max-flow, we can get the value $v(f)$ immediately, and all the configuration directly from the original graph.

In the aspect of min-cut, the value is simply equals to the max-flow value $v(f)$, and the cut configuration itself can be found in the final residual graph: Start from $s$, include all nodes which are reachable from $s$.

4.4 Complexity

The runtime complexity of Ford-Fulkerson is $O(mC)$, where $m$ is the number of edges and $C$ is the maximum flow in the graph. This is because the flow value increase at least 1 after each iteration, and for each iteration we use DFS or BFS to find the augmenting path which takes $O(m+n)=O(m)$ time. Therefore, the total time complexity is $O(mC)$.

5. Circulation with Demands

In former flow network, we only have one source $s$ and on sink $t$. Now in this case we suppose that there can be a set $S$ of sources and a set $T$ of sinks that can absorb flow. As before, there is an integer capacity on each edge.

In this case, it is not clear how to decide a max-flow of the graph. So instead of maximizing the flow value, we consider a problem where sources have fixed supply values and sinks have fixed $demand$ values, and our goal to satisfy all demands using the available supply.

5.1 Circulation

Given a digraph $G=(V,E)$ with nonnegative edge capacities $c(e)$ and node supply and demands d(v), a circulation is a function that satisfies:

• For each $e\in{E}: 0\leq{f(e)}\leq{c(e)}$
• For each $v\in{V}: \sum\limits_{e\ into\ v} f(e) - \sum\limits_{e\ out\ of\ v} f(e) = d(v)$

Now instead of considering a maximization problem, we are concerned with a feasibility problem: We want to know whether there exists a circulation that meets the two conditions above.

5.2 Problem Reduction

Actually, this problem can be reduce to a max-flow problem by following procedure:

First of all we give each node $v\in{V}$ a demand value $d_v$, each source node (supply) has a negative integer value, each sink node has a positive integer value, and each internal node has demand 0.

Secondly we add a "super-source" node $s^*$ and a "super-sink" node $t^*$. Then we draw an edge from $s^*$ to each original source nodes $s$ with capacity of the source's demand value. Also, we draw an edge from each sink node to $t^*$ with capacity of the sink's demand value.

Finally this problem have been reduced to a max-flow problem, we can us Ford-Fulkerson algorithm to compute a max-flow configuration. At last we check if $\sum\limits_{v\in{B}} d(v)>cap(A,B)$ then there does not exist a circulation, otherwise there is a circulation.

5.3 Circulation with demands and lower bounds.

In previous problems for each edge $e\in{E}$ we all have condition $0\leq{f(e)}\leq{c(e)}$. However in this case we also place a lower bound $l(e)$ on each edge.

This problem can be reduced to the circulation with demands problem then be reduced to the max-flow problem. Given an edge $(u,v)$ in $G$ with a lower bound $l(e)$ and an upper bound $c(e)$, we modify the demand value of $u,v$ to $d(u)' = d(u) + l(e), d(v)' = d(v) - l(e)$ to get $G'$. And that's it, and the theorem is: There exists a circulation in G iff there exists a circulation in G'. Moreover, if all demands, capacities, and lower bounds in G are integers, then there is a circulation in G that is integer-valued.

---

Acknowledgement:

This article is my learning notes of course CS331 Algorithms and Complexity (Spring 2014), lectured by Prof. Greg Plaxton.