The Maximum Network Flow Problem
Let’s begin with some key ideas about the network flow problem and relevant concepts.
Given a directed graph $G=(V,E)$, a source node $s \in V$, and a sink node $t \in V$. For each $e \in E$, there is a capacity, denoted as $c(e)$ or $c(u,v)$. When $(u,v) \notin E $, we assume $c(u,v)=0$.
Our goal for the maximum flow problem is to push as much flow as possible from $s$ to $t$ in the graph (network). The rules are that no edge can have flow exceeding its capacity, and for any vertex except $s$ and $t$, the in to the vertex must equal the flow out from the vertex. That is,
Capacity constraint: For any edge $e \in E$, we have $0 \leq f(e) \leq c(e)$.
Flow conservation: For any vertex $u \in (V \setminus \lbrace s,t\rbrace)$, $\sum_{x\in V}f(u,x)=\sum_{x\in V}f(x,u)$.
And a flow that satisfies such requirements is called a feasible flow. What we want is to maximize the flow from $s$ to $t$. We can measure it by: $$ |f|=\sum_{u\in V}f(s,u)-\sum_{u\in V}f(u,s) $$ You may notice that what we are really measuring is the net flow that out of $s$, and we can easily prove that it is the same as the net flow that into $t$.
Let’s take the following graph/network as an example, the number on the edge is the capacity of that edge. Please take some time and try to figure out the maximum network flow for this network.
The correct answer is 5. Where do the 5 come from? Let’s start with the simplest feasible flow, the all-zero flow. This flow is feasible since it meets all the requirements mentioned above. But obviously, it’s not the maximum network flow. We can formally tell it’s not the maximum by finding another path that has more flow from $s$ to $t$ (actually there are many such paths.) For instance, the path $s\to a \to c\to t$ can contain at least 2 flows. So here gives us a hint: A flow is not optimal if there is another $s$-$t$ path with available capacity.
$s$-$t$ cuts
The above finding helps us tell a flow is not maximum, but how can we know a flow is actually maximum? We can’t be certain that we haven’t made a bad decision and dropped into a sub-optimal path. Notice that the edges $a\to c$ and $s\to b$ are taken up all the capacity, and if we remove them, then we disconnect $t$ from $s$. In other words, the network has an “$s$-$t$ cut” of capacity of 5. Because we must go through these edges for the path goes from $s$ to $t$ (we can’t bypass them for having more capacity), so we know we’re optimal.
We can formalize this idea:
For a network $G=(V,E)$, if $\lbrace S,T\rbrace$ is a partition of $V$ (namely $S\cup T=V$ and $S\cap T=\varnothing$) and $s\in S, t\in T$, then we call $\lbrace S,T\rbrace$ is an $s$-$t$ cut of $G$.
We define the capacity of $\lbrace S,T\rbrace$ is: $$ ||S, T|| = \sum_{u \in S} \sum_{v \in T} c(u, v) $$ and the net flow across a cut $\lbrace S,T\rbrace$ is: $$ f(S,T)=\sum_{u \in S} \sum_{v \in T} f(u, v)-\sum_{u \in S} \sum_{v \in T} f(v, u) $$
We can easily notice that the value of a flow $|f|$ is equivalent to the net flow across the cut $\left\lbrace \lbrace s \rbrace,V\setminus \lbrace s \rbrace \right\rbrace$. Actually the net flow across any cut is equal to the flow value $|f|$, you can prove this by using the definition above.
Plus, we may notice that the value of any $s$-$t$ flow is less than the value of any of $s$-$t$ cut. So, we can argue:
The value of any $s$-$t$ flow $\leq$ maximum $s$-$t$ flow $\leq$ minimum $s$-$t$ cut $\leq$ the capacity of any $s$-$t$ cut
This means if we can find an $s$-$t$ flow that equals the value of any cut, then we know we’ve found the maximum flow.
Finding a maximum flow
So now we can design a workflow to find the maximum flow. The intuitive strategy is:
- Find a path from $s$ to $t$, and push as much flow on it as possible.
- Look at the leftover network, if it has at least a $s$-$t$ path, then repeat 1.
At the end, there isn’t any path with the capacity to push any additional flow on. But is it the right strategy? Unfortunately not. Let’s look at the following example, where the algorithm has already decided to push 1 unit flow to the path $s\to a\to b\to t$
In this case, we can’t find any $s$-$t$ path with available capacity left, but it is not a maximum flow as well.
The reason why we encounter such a problem is that we mistakenly sent a flow from $a$ to $b$. So in order to achieve the optimal solution, we need a way of “undoing” such mistakes. Here comes the residual capacity, which gives us an opportunity to undo the bad decisions. This is the key idea of the Ford-Fulkerson algorithm.
The Ford-Fulkerson algorithm
As mentioned above, the idea behind the Ford-Fulkerson algorithm is “undoing” bad previous decisions. To achieve this, we need to make some changes to introduce the concept of residual capacity and the residual graph/network.
Firstly, instead of only taking account of the capacity $c(u,v)$ where $(u,v)\in E$, we’re going to allow for the possibility of the $c(u,v)$ and $c(v,u)$ in either direction. This makes intuitive sense since we can treat the edges as pipes between two nodes, where we don’t know which way we would push the flow. Secondly, if there is a flow $f(u,v)>0$ along some edge, then the flow in the other direction $f(v,u)=0$. Since if it were the case that both of the flows were positive, we could replace the smaller one with zero and the bigger one with their difference.
Now we can have the formal definition of residual capacity and the residual graph/network
Residual capacity: Given a flow $f$ in graph $G$, the residual capacity of an edge $(u,v)\in E$ is $$ \begin{align} c_f(u,v)&=c(u,v)-f(u,v)\\ c_f(v,u)&=c(v,u)+f(u,v) \end{align} $$ Residual graph/network: Given a flow $f$, the residual graph/network $G_f$ is the directed graph with all edges of positive residual capacity, namely $G_f=(V,E_f)$, where $E_f=\left\lbrace(u,v)\mid c_f(u,v)>0\right\rbrace$.
We call an $s$-$t$ path in the residual graph as an augmenting path, as we can use it to augment the existing flow. Why is this useful? Well, when $(u,v)\in E$, the residual capacity on the edge is the same as our original intuitive notion of the “leftover” capacity. The second case is the magic that makes the Ford-Fulkerson algorithm work. If we’ve pushed some flows on $(u,v)$, then we are still able to undo that by pushing flow back in the reverse direction $(v,u)$. For example, consider the residual graph of the suboptimal flow from earlier:
Unlike before, now we can find a $s$-$t$ path $s\to b\to a \to t$, and this path undoes the mistaken flow from $a$ to $b$. Therefore, we can achieve the optimal maximum flow.
So as long as there is an augmenting path $P$ on $G_f$, then we can push the maximum possible flow along $P$. If there isn’t any augmenting path, which means we achieve the maximum flow. This is the whole process of the Ford-Fulkerson algorithm.
The Analysis
The time complexity of the Ford-Fulkerson algorithm is easy to get, since we just use the plain greedy and brute force. For each iteration, we can implement a $O(n+m)$ DFS (or BFS), and the maximum iteration time equals the maximum flow $|f|$, so the overall complexity is $O((n+m)|f|)$. Because the graph should be connected, which means $m\geq n-1$, thus the complexity can be written as $O(m|f|)$. We will discuss how to optimize it later, now let’s talk about the correctness.
As we said earlier, the Ford-Fulkerson algorithm will stop as long as there isn’t any augmenting path, in other words, $s$ and $t$ disconnected on the final residual graph. Let $S$ be the set of vertices that can be reached from $s$ in the residual graph, and let $T$ be the rest of the vertices.
It is obvious that $t\in T$, otherwise $s$ should be connected to $t$, so it is a valid $s$-$t$ cut. Let $c=||S, T||$, the capacity of the cut in the original graph; in the residual graph, it should be $0$ (think about the reason.) From the earlier discussion, we know that $|f|=f(S,T)\leq c$. Therefore, we know we’ve found the maximum flow if we find a flow of $c$. Let’s consider both cases:
- Consider the edge $(u,v)\in E$, where $u\in S, v\in T$. We know that such an edge must be at the maximum capacity (saturated). Because otherwise there is a $s$-$t$ path in the residual graph, the algorithm shouldn’t stop.
- Consider the edge $(v,u)\in E$, where $u\in S, v\in T$. Such an edge must be empty. Suppose we have a non-zero flow on such an edge $(u,v)$, from the definition of the residual capacity, we know that $c_f(u,v)>0$. It shouldn’t happen since this would tell us there is a path to reach a vertex in $T$.
Thus, we have: $$ \begin{align} |f|=f(S,T)&=\sum_{u \in S} \sum_{v \in T} f(u, v)-\sum_{u \in S} \sum_{v \in T} f(v, u)\\ &=\sum_{u \in S} \sum_{v \in T} c(u, v)-\sum_{u \in S} \sum_{v \in T} 0\\ &=\sum_{u \in S} \sum_{v \in T} c(u, v)\\ &=c&\square \end{align} $$ It also proves the famous maximum-flow minimum-cut theorem:
In any flow network $G$ , for any two vertices $s$ and $t$ , the maximum flow from $s$ to $t$ equals the capacity of the minimum $s$-$t$ cut.
Edmonds–Karp algorithm
The plain Ford-Fulkerson algorithm spends a lot of time on iterations of finding an augmenting path. Edmonds-Karp algorithm provides a way to choose a better augmenting path than the arbitrary ones. That is, we select the shortest $s$-$t$ path in the residual graph as the augmenting path, where each edge has unit distance. Now let’s prove the algorithm runs in $O(nm^2)$ time.
Let $d_f(u)$ be the (shortest-path) distance from $s$ to $u$ in $G_f$.
Lemma 1: For all vertices $u \in (V \setminus \lbrace s,t\rbrace),\ d_f(u)$ increases monotonically with flow augmentation.
Proof: Assume that for some vertex $u \in (V \setminus \lbrace s,t\rbrace)$, there is a flow augmentation that causes the distance from $s$ to $u$ to decrease. Let the flow $f$ be the flow before the augmentation that decreases the distance, and $f’$ be the flow afterward. Let $v$ be the vertex with the minimum $d_{f’}(v)$ whose distance was decreased by the augmentation, that is, $d_f(v)>d_{f’}(v)$. Let $p=s\leadsto u\to v$ be the shortest path from $s$ to $v$ in $G_{f’}$, so that $(u,v)\in E_{f’}$ and $d_{f’}(u) = d_{f’}(v) - 1$.
Because $d_{f’}(u)<d_{f’}(v)$, there is no chance that the distance from $s$ to $u$ can be decreased, namely, $d_f(u) \leq d_{f’}(u)$.
We claim that $(u,v)\notin E_f$, because if we had $(u,v)\in E$, then we would have $$ \begin{align} d_f(v)&\leq d_f(u)+1\\ &\leq d_{f’}(u)+1\\ &=d_{f’}(v) \end{align} $$ which contradicts the assumption of $d_f(v)>d_{f’}(v)$.
The only way that we can have both $(u,v)\notin E_f$ and $(u,v)\in E_{f’}$ is that the augmentation has increased the flow on the edge $(v,u)$. Because the Edmonds-Karp algorithm always augments the flow along the shortest path, the shortest path from $s$ to $u$ in $G_f$ has $(v,u)$ as the last edge. Therefore, $$ \begin{align} d_f(v)&=d_f(u)-1\\ &\leq d_{f’}(u)-1\\ &=d_{f’}(v)-2 \end{align} $$ which also contradicts the assumption of $d_f(v)>d_{f’}(v)$. We conclude that our assumption of such $v$ doesn’t exist. $\square$
Lemma 2: The total number of flow augmentations is $O(nm)$.
Proof: Each iteration saturates at least one edge, and when the edge is saturated, it can’t be used again unless the reversed edge is used.
Since augmenting paths are always shortest paths, when $(u,v)$ is saturated for the first time, we have $d_f(v)=d_f(u)+1$. If the reversed edge becomes a part of the new augmenting path. Let’s say $f’$ is the flow when this happens, then we have $d_{f’}(u) = d_{f’}(v)+1$. From Lemma 1, we know $d_{f’}(v)\geq d_f(v)$. Therefore, $$ \begin{align} d_{f’}(u)&=d_{f’}(v)+1\\ &\geq d_f(v)+1\\ &=d_f(u)+2 \end{align} $$ As a result, the distance of $s$ from the source will be increased by at least 2 units once the edge $(u,v)$ is saturated again. Since $d(s)$ is initially at least 1, and at most $n-1$. The edge $(u,v)$ can be saturated at most $\cfrac{n-1-1}{2}+1=\cfrac{n}{2}$ times. As there are $m$ pairs of vertices that can have an edge between them, the total number of edges that are saturated during the entire execution is $O(nm)$. Each augmenting path has at least one saturated edge, therefore, the lemma holds. $\square$
Because for each iteration, we implement a $O(m)$ BFS to find the augmenting path, the overall time complexity of the Edmonds–Karp algorithm is $O(nm^2)$.