by Vernon

(Adapted from the NOI.PH 2017 IOI training.)

## Introduction

Many interesting real-life situations can be modelled as a flow network problem. There are also lots of interesting theoretical problems that can be reduced to problems on flow networks. For these reasons, it is one of the most important and widespread topics in computer science. In fact, due to the sheer number of applications, it can be considered a “paradigm” on its own, along with dynamic programming, greedy, etc.

Although this topic is explicitly excluded from the IOI syllabus, most IOI competitors are familiar with it. Many flow algorithms use some basic graph algorithm (such as DFS, BFS, Dijkstra, or Bellman-Ford) as a subroutine. Hence, studying these algorithms forces one to practice these and generally improves your skills in solving graph problems. In addition, bipartite matching is included in the IOI syllabus, and although there are ways to solve bipartite matching without using flow networks, studying the flow network reduction deepens your understanding of bipartite matching. It will thus be helpful to study this topic for the IOI.

You may first watch these lectures from MIT or these lectures from Stanford to get an intuition for the concepts before reading the text below for details and rigor. The MIT lectures are based on the CLRS formulation of network flows, while the Stanford lectures are roughly based on the Kleinberg and Tardos formulation. The MIT/CLRS material go for rigorous proofs while the Stanford material discuss more algorithms, applications, and generalizations. I personally prefer the Stanford material, but the MIT material is also valuable for exposure to a slightly different approach. The text below tries to be as complete as the Stanford material while being as rigorous as the MIT/CLRS material, but is independent of either. In addition, it also goes into the practical aspects of implementation and solving programming contest problems. It relies on and is meant to be read along with these slides from Princeton. Just follow the text, and it will prompt you to open a link to look at the slides with the specified pages for illustrations. The empirical comparisons and conclusions below are based on this article from TopCoder. There are several factual errors in that article, but I trusted the validity of the experiments. The conclusions below can be wrong if the experiments turn out to be flawed.

## The Maximum Flow Problem and the Minimum Cut Problem

### Basic Definitions

Let's say we have a directed graph $G = (V, E)$ with a special structure. There is a special node $s \in V$ called the source, whose in-degree is 0, and another special node $t \in V$ called the sink, whose out-degree is 0. We will further assume that our graph is simple (there are no self-loops and parallel edges between the same nodes), and that there is at least one edge incident to every node. (A practice problem later will force you to think about how to get around some of these assumptions.) Additionally, for each edge $e \in E$, we assign a non-negative capacity $c(e)$. A graph that satisfies all these properties is called a flow network.

Take a look at I.3 for a visualization of a flow network.

Intuitively, a flow network represents “stuff” (water, electricity, etc.) that can flow from one location to another via pipes. Stuff is produced at a special location called the source, and is consumed at another special location called the sink. Each pipe imposes a certain limit on the volume of stuff that can pass through it at any given point in time. A natural question to ask is the following: what is the maximum rate of flow from the source to the sink?

More formally, let us define an st-flow (or just a flow) as a function $f: E \mapsto N$ that assigns an integer to each edge, respecting the following two constraints:

• Capacity constraint: for each $e \in E$, $0 \leq f(e) \leq c(e)$
• Flow conservation constraint: for each $v \in V - \{s, t\}$, $\sum\limits_{e \text{ in to } v} f(e) = \sum\limits_{e \text{ out of } v} f(e)$

If $f(e) = c(e)$, we say that edge $e$ is saturated with respect to flow $f$.

Take a look at I.7 for a visualization of a valid flow defined on the network you just saw. You can check that the capacities are respected and flow is conserved for the edges and the node $v$ highlighted in blue.

We define the value of the flow as the sum of the flow values assigned to all edges going out of the source, $val(f) = \sum\limits_{e \text{ out of } s} f(e)$. The maximum flow problem is to find a flow of maximum value.

Exercise. What is the value of the flow we just defined? See I.8 for the answer.

Exercise. Is this the maximum possible value for this network? If no, what is? See I.9 for the answer.

Let's momentarily turn our attention to another problem. Interpret the capacity of each edge as the cost of removing the edge from the graph. Another interesting question would be: what is the least total cost to hijack the network, to disconnect the source from the sink and completely prevent the stuff from flowing from the source to the sink?

More formally, let us define an st-cut (or just a cut) as a partition $(A, B)$ of the vertices with $s \in A$ and $t \in B$. The capacity of the cut $cap(A, B)$ is the sum of the capacities of the edges from $A$ to $B$:

Take a look at I.4-I.5 to see examples of cuts.

The minimum cut problem is to find a cut of minimum capacity.

Exercise. What is the minimum capacity cut of our graph? See I.6 for the answer.

On first glance, these two problems appear to be unrelated. But in fact, we shall see later that they are essentially the same problem, both solvable using the same algorithms. It is no coincidence that the value of the maximum flow and the capacity of the minimum cut are the same for our given graph.

We will solve the max-flow problem first, and then see how to apply the same solution to the min-cut problem.

Exercise. Before looking at the algorithm below, think about how you might approach this problem.

### Incremental Improvement: Augmenting Paths (Ford-Fulkerson)

A very natural approach to getting the maximum flow would be the following:

1. Start with an empty flow: let $f(e) = 0$ for all $e \in E$.
2. Find an $s \sim t$ path $P$, where for each edge $e$ along $P$, $f(e) < c(e)$. (Find a path of unsaturated edges.)
3. Augment the flow along $P$: for each edge $e$ along $P$, increase $f(e)$ by the bottleneck capacity $\min\limits_{e \in P} c(e) - f(e)$. (Saturate the minimum-remaining-capacity edges (bottleneck edges) in $P$.)
4. Repeat until there are no more such paths.

The idea is that we start with an obviously non-optimal answer but which surely satisfies the constraints, and then converge towards the optimum by incremental improvements that still respect the constraints. Take a look at I.13-I.15 for a sample run of this algorithm.

Exercise. Does this correctly find the maximum flow? Find a counterexample. See I.16 for an answer.

Our approach fails because it is too greedy. Ideally, what we want is to have some way to “undo” certain flow increases. Look at I.15 again. If we can somehow increase the flow by one unit across the edge going out of $s$ labeled 6/10, undo pushing one unit of flow across the edge labeled 2/2, and finally redirect that one unit of flow towards the edge labeled 0/4 and then towards the edge going into $t$ labeled 6/10, we still satisfy the capacity and flow conservation constraints, but strictly increase the flow value by one. To reach the optimal answer, we can do this once more, and then another time involving the edge labeled 8/8 instead. In other words, what we really want is to be able to push flow “forward” normally, but also to be able to push flow “backward” along the reverse of edges that already have flow going forward. We still successively augment along $s \sim t$ paths, but we now allow the usage of backward edges as part of the paths. The intuitive reason why this works is as follows. Performing a “backward” push along some edge $e = (u, v)$ amounts to splitting a previously constructed path $P = s \sim t$ into two parts: $P_1 = s \sim u$ and $P_2 = v \sim t$. It similarly splits our new path $P' = s \sim t$ into $P'_1 = s \sim v$ and $P'_2 = u \sim t$. In order for the augmentation along $P'_1$ to be valid, respecting the conservation constraint on $v$, the flow from $u$ to $v$ is undone and redirected elsewhere, in particular to $P'_2$. This allows us to “reconstruct” an augmenting path $P'_1 + P_2$. But since we take away $P_2$ from $P$, we have to ensure that $P_1$ can still connect to the sink to be a valid augmenting path, and that the conservation constraint on $u$ is respected. Redirecting the flow to $P'_2$ achieves this for us, allowing us to “reconstruct” another augmenting path $P_1 + P'_2$.

The concept of a residual graph gives us a clean way to keep track of these forward and backward pushes. Given a flow network $G = (V, E)$ with edge capacities $c$ and a flow $f$, we define the residual capacity $c_f(e)$ of some $e = (u, v)$ with respect to $f$ as follows:

$$c_f(e) = \begin{cases} c(e) - f(e) & e = (u, v) \in E\\ f(e) & e^R = (v, u) \in E \end{cases}$$

An edge $e$ is a residual edge with respect to $f$ iff $c_f(e)$ is defined. Finally, we define the residual graph $G_f = (V, E_f)$ of $G$ with respect to $f$ as the graph with the same node set, and whose edge set is the set of residual edges $e \in E_f$ iff $c_f(e)$ is defined. Intuitively, the residual graph consists of edges which we can still use for augmentation: forward edges $e$ with “leftover” capacity $c(e) - f(e)$, and backward edges $e$ through which we can “undo” $f(e)$ units of flow that have previously been pushed forward in the opposite direction $e^R$. See I.17 for an example.

We now have a simple algorithm, invented by Ford and Fulkerson in 1955, for finding the maximum flow.

1. Start with an empty flow: let $f(e) = 0$ for all $e \in E$.
2. Find an $s \sim t$ path $P$ in the residual graph $G_f$, where for each edge $e$ along $P$, $c_f(e) > 0$. We call this an augmenting path.
3. Let $b = \min\limits_{e \in P} c_f(e)$ be the bottleneck capacity of $P$.
4. Augment the flow along $P$: for each edge $e$ along $P$, if $e$ is a forward edge ($e \in E$), increase $f(e)$ by $b$, otherwise decrease $f(e^R)$ by $b$ (as $e$ is a backward edge).
5. Repeat until there are no more such paths.

See I.23-I.25 for a demo.

Is this algorithm correct? To prove it, we need to prove three things:

1. Augmentation never violates the capacity and conservation constraints.
2. The algorithm always terminates.
3. At termination, the value of the flow is maximum.

Statements 1 and 2 are quite easy to prove. Statement 3 is more subtle, and leads us into proving the equivalence of max-flow and min-cut, and that we also now have an algorithm for solving the min-cut problem. But first, try proving statements 1 and 2 and try implementing the algorithm.

Problem. Given a flow network $G$, prove that if $f$ is a flow, then the function $f' = Augment(f, P)$ obtained by augmenting the flow $f$ along an augmenting path $P$ in the residual graph $G_f$ is also a flow. In particular, verify that the capacity and conservation constraints are respected. (Hint: Since the $f$ is changed only for the edges along $P$, you only need to verify that the constraints are respected for these edges. Consider forward and backward edges separately.)

Problem. Prove that the flow value strictly increases at every augmentation.

Problem. Let $C = \sum\limits_{e \text{ out of } s} c(e)$. Prove that the Ford-Fulkerson algorithm can be implemented to run in $O(EC)$ time. (Hint: Recall that we assumed that there is at least one edge incident to every node.)

Exercise. Try implementing your own version of Ford-Fulkerson first before comparing it with the implementation below. Test it on this problem: UVa 820 - Internet Bandwidth. Don't forget to print a blank line after each test case.

Here is a simple implementation of the Ford-Fulkerson algorithm. Either DFS or BFS can be used to find augmenting paths. This implementation uses DFS, chosen arbitrarily.

#include <bits/stdc++.h>
#define MAX_N 100
#define INF 1'000'000 // a VERY useful C++14 feature
using namespace std;
int n, m, s, t;
int c[MAX_N+1][MAX_N+1];
int f[MAX_N+1][MAX_N+1];
int p[MAX_N+1]; // "parent" in the DFS tree, needed for retrieving the augmenting path
bool dfs(int u) {
if(u == t) return true;
// p[v] == -1 implies not discovered, c[u][v] - f[u][v] is the residual capacity
if(p[v] == -1 && c[u][v] - f[u][v] > 0) {
p[v] = u;
if(dfs(v)) return true;
}
}
return false;
}
bool find_aug_path() {
memset(p, -1, sizeof p);
p[s] = 0; // dummy to mark the source as discovered
return dfs(s);
}
int main() {
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
// assume input is of the following format:
// $n$ (number of vertices) $s$ (source) $t$ (sink) $m$ (number of edges)
// $u_1$ $v_1$ $capacity_1$
// $u_2$ $v_2$ $capacity_2$
// ...
// $u_m$ $v_m$ $capacity_m$
cin >> n >> s >> t >> m;
for(int i = 0; i < m; i++) {
int u, v, capacity;
cin >> u >> v >> capacity;
adj[v].insert(u); // so that backward edges are included in the DFS
// parallel edges are handled by just combining them into a single edge,
// whose capacity equals the total of the capacities of the parallel edges
c[u][v] += capacity;
// c[v][u] += capacity; // for undirected graphs
}
int max_flow_value = 0;
while(find_aug_path()) {
int b = INF;
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) b = min(b, c[u][v] - f[u][v]);
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) f[u][v] += b, f[v][u] -= b;
max_flow_value += b;
}
cout << max_flow_value << endl;
return 0;
}


Here it is again, with the comments removed, just to highlight how short and simple the algorithm really is.

#include <bits/stdc++.h>
#define MAX_N 100
#define INF 1'000'000
using namespace std;
int n, m, s, t;
int c[MAX_N+1][MAX_N+1];
int f[MAX_N+1][MAX_N+1];
int p[MAX_N+1];
bool dfs(int u) {
if(u == t) return true;
if(p[v] == -1 && c[u][v] - f[u][v] > 0) {
p[v] = u;
if(dfs(v)) return true;
}
}
return false;
}
bool find_aug_path() {
memset(p, -1, sizeof p);
p[s] = 0;
return dfs(s);
}
int main() {
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cin >> n >> s >> t >> m;
for(int i = 0; i < m; i++) {
int u, v, capacity;
cin >> u >> v >> capacity;
c[u][v] += capacity;
}
int max_flow_value = 0;
while(find_aug_path()) {
int b = INF;
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) b = min(b, c[u][v] - f[u][v]);
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) f[u][v] += b, f[v][u] -= b;
max_flow_value += b;
}
cout << max_flow_value << endl;
return 0;
}


Let's notice a few things about this implementation. First, notice that we do not have to explicitly construct $G_f$, as just by keeping track of $c$ and $f$, we can easily infer $c_f$ for path finding. Second, notice that the way we define the residual capacity is slightly different here. We simply use $c(e) - f(e)$ and do not discriminate the forward and backward directions. We recover the original definition by defining $c(e)$ to be $0$ and by allowing $f(e)$ to be negative on backward edges. The augmentation procedure is also slightly modified to always increment the forward direction and to always decrement the backward direction. We do this to simplify the implementation and also to be able to handle anti-parallel edges (edges between the same nodes but in opposite directions). Take a moment to convince yourself that this works, and that the previous definition does not work for anti-parallel edges but this one does. There are other ways to deal with parallel and anti-parallel edges but this is the one I find the simplest, though slightly non-intuitive. Also notice that we use an adjacency set instead of an adjacency list here, to avoid storing duplicate neighbors due to parallel edges. Finally, this implementation is not the most memory-efficient possible one, but as we will see later, the running time of all practical maximum flow algorithms are all $\Omega(n^3)$, where $n$ is the number of nodes in the graph. This means that max-flow approaches to a problem are practical in terms of time iff using $O(n^2)$ memory is practical. Hence, it does not matter that we use $O(n^2)$ memory here. It makes the implementation simpler and require less time to run (which is more important for max-flow-related problems). In cases where the memory limit is really tight (e.g. max-flow is only part of the problem, and the other parts need the memory), it is fairly trivial to change this implementation to use a linear amount of memory.

### The Max-Flow Min-Cut Theorem

We now prove that the Ford-Fulkerson algorithm yields the maximum flow. As a side effect, we also prove the equivalence of max-flow and min-cut.

The idea is to find a tight upper bound on what the value of the max-flow can be, and to show that the Ford-Fulkerson algorithm indeed reaches this bound. One such bound is an obvious one: the value of a flow is always less than or equal to the sum of the capacities of the edges going out of the source, $val(f) \leq \sum\limits_{e \text{ out of } s} c(e)$. It is not tight enough to be helpful for proving anything, but the intuition behind this bound is helpful and can be generalized. Rather than considering just the sum of the capacities going out of the source, let's generalize to any “moat” around the source, and consider the sum of the capacities going out of this “moat” (more formally, a cut). It makes intuitive sense that the value of a flow must be smaller than this sum, and we state this as Lemma 2. To prove it formally, we need the following lemma first.

Lemma 1. (Flow Conservation Across Cuts) Let $f$ be any flow and let $(A, B)$ be any cut. Then the net flow across $(A, B)$ equals the value of $f$. $$\sum_{e \text{ out of } A} f(e) - \sum_{e \text{ in to } A} f(e) = val(f)$$

See I.28-I.30 for examples of what this lemma is saying.

Exercise. Prove Lemma 1. (Hint: Use the flow conservation constraint.) See I.31 for the answer.

Problem. As a simple application of Lemma 1, prove that the value of the flow is equivalent to (and thus may also be alternatively defined as) the sum of the flows of the edges going into the sink: $val(f) = \sum\limits_{e \text{ out of } s} f(e) = \sum\limits_{e \text{ in to } t} f(e)$.

Using Lemma 1, we can now prove a stronger bound on the value of the flow.

Lemma 2. (Weak Duality Between Flows and Cuts) Let $f$ be any flow and let $(A, B)$ be any cut. Then the value of the flow is less than or equal to the capacity of the cut. $$val(f) \leq cap(A, B)$$

Let's think carefully about what Lemma 2 is saying. It is actually saying something quite strong: the value of any flow is always less than or equal to the capacity of any cut. In particular, this means that the max-flow value is less than the min-cut capacity. If we can somehow produce a flow $f$ and a cut $(A, B)$ where $val(f) = cap(A, B)$, then we know that $f$ is a max-flow, and $(A, B)$ is a min-cut. It turns out that the Ford-Fulkerson algorithm indeed produces a flow with this property. If we prove this, we both prove that the Ford-Fulkerson algorithm correctly finds the maximum flow and that max-flow is equivalent to min-cut (and by extension, that the Ford-Fulkerson algorithm also allows us to find the minimum cut).

Lemma 3. (No Augmenting Paths Implies Existence of Cut Equivalent to Flow) Let $f$ be a flow such that there are no $s \sim t$ paths in the residual graph $G_f$. Then there is a cut $(A, B)$ where $val(f) = cap(A, B)$.

Problem. Let $A$ be the set of nodes reachable from the source using residual edges in $G_f$ above, and let $B = V - A$. Prove that $(A, B)$ is a cut (i.e. that they are disjoint, that $s \in A$, and that $t \in B$).

Problem. Consider an edge $e = (u, v)$ where $u \in A$ and $v \in B$. Prove that $f(e) = c(e)$.

Problem. Consider an edge $e = (u, v)$ where $v \in A$ and $u \in B$. Prove that $f(e) = 0$.

The above two statements imply that all edges out of $A$ are completely saturated with flow, while all edges in to $A$ are completely empty.

Problem. Use the above facts, together with Lemma 1, to prove Lemma 3.

Lemma 2 and Lemma 3 easily imply the following corollary.

Corollary 4. (No Augmenting Paths Implies Maximum Flow, Minimum Cut) Let $f$ be a flow such that there are no $s \sim t$ paths in the residual graph $G_f$. The value of $f$ is maximum over all possible flows in $G$. The capacity of the cut $(A, B)$ whose existence is guaranteed by Lemma 3 and whose capacity is equal to the value of $f$ is minimum over all possible cuts in $G$.

Since the Ford-Fulkerson algorithm only terminates when there are no more $s \sim t$ paths in the residual graph, its correctness easily follows from Corollary 4.

Theorem 5. (Correctness of Ford-Fulkerson) The flow produced by the Ford-Fulkerson algorithm is a maximum flow.

The Ford-Fulkerson algorithm guarantees that in every flow network, there is a flow $f$ and a cut $(A, B)$ where $val(f) = cap(A, B)$, which immediately implies the following famous theorem.

Theorem 6. (Max-Flow Min-Cut Theorem) In every flow network, the maximum value of a flow is equal to the minimum capacity of a cut.

This beautiful relationship between flows and cuts is an example of the more general mathematical principle of duality}.

See I.33-I.35 for a slightly different proof.

Exercise. After applying the Ford-Fulkerson algorithm to find the maximum flow, how would you produce the actual minimum-capacity cut (partition) $(A, B)$?

### Finding Augmenting Paths Smartly: Shortest Augmenting Paths (Edmonds-Karp)

We have seen a very simple algorithm for solving the max-flow min-cut problem. Unfortunately, we have only proven that it runs in $O(EC)$.

Exercise. Prove another bound on the running time of Ford-Fulkerson: $O(EF)$, where $F$ is the output maximum flow value.

Both of these bounds can be bad for certain instances of the problem where the edge capacities are large. In fact, we technically do not yet have a polynomial-time algorithm, as time complexity is measured in the number of bits of input, and $C$ (likewise $F$) is exponential in $\lg C$ (likewise $\lg F$), which is the number of bits required to represent the edge capacities. (Don't fret if you don't quite understand why time complexity is measured this way. This is a fine technical point.)

Exercise. Come up with an instance of the max-flow problem that causes the Ford-Fulkerson algorithm to actually require $\Omega (EC)$ amount of time. See I.38 for the answer.

An interesting but completely useless side note: the Ford-Fulkerson algorithm is not even guaranteed to terminate if the capacities are irrational numbers!

To improve the Ford-Fulkerson algorithm, we need to have a good way of finding augmenting paths. Intuitively, it makes sense that we need both an efficient path-finding algorithm, and one which leads to the fewest possible iterations of augmentation. The first condition leads us to consider finding augmenting paths with the fewest number of edges, the shortest augmenting paths. Fortunately, this is very simple to achieve. Just use BFS to find augmenting paths. The idea is, unlike with DFS, where the path to the sink can be long, with BFS, we can stop early when we discover the sink, and maybe that leads to a faster algorithm. Surprisingly, it is the second of the two conditions above (fewest possible iterations of augmentation) which we actually fulfill. The difference between DFS and BFS turns out to not matter too much for any single particular iteration (and hence there is no real need to stop the BFS early), but makes a difference globally, when we consider the running time of all the iterations together. This was invented by Edmonds and Karp in 1972. The improvement itself is not hard to invent. It is the proof that it actually works and makes the running time strictly polynomial that is difficult and which these two guys got credit for.

If you randomly picked DFS instead of BFS on your first attempt to implement the Ford-Fulkerson algorithm, now is your chance to redo and solve UVa 820 - Internet Bandwidth, before comparing with the implementation below.

Here is an implementation of the Edmonds-Karp algorithm. Notice that the only thing that changes from above is the usage of BFS instead of DFS. Everything else (residual capacities, finding the bottleneck, updating the flow) stay the same.

#include <bits/stdc++.h>
#define MAX_N 100
#define INF 1'000'000
using namespace std;
int n, m, s, t;
int c[MAX_N+1][MAX_N+1];
int f[MAX_N+1][MAX_N+1];
int p[MAX_N+1];
bool bfs() {
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
if(p[v] == -1 && c[u][v] - f[u][v] > 0) {
p[v] = u;
q.push(v);
}
}
}
return p[t] != -1;
}
bool find_aug_path() {
memset(p, -1, sizeof p);
p[s] = 0;
return bfs();
}
int main() {
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cin >> n >> s >> t >> m;
for(int i = 0; i < m; i++) {
int u, v, capacity;
cin >> u >> v >> capacity;
c[u][v] += capacity;
}
int max_flow_value = 0;
while(find_aug_path()) {
int b = INF;
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) b = min(b, c[u][v] - f[u][v]);
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) f[u][v] += b, f[v][u] -= b;
max_flow_value += b;
}
cout << max_flow_value << endl;
return 0;
}


Why does this simple change make a big difference? Let's now try to analyze the running time of the shortest augmenting paths algorithm. First, we need to prove some lemmas.

Lemma 7. (Monotonically Non-Decreasing Distances) Throughout the shortest augmenting paths algorithm, the distance from the source to any node in the residual graph never decreases from one iteration to the next.

You can convince yourself of this by running the algorithm on a few graphs and printing out the paths found by the algorithm in each iteration, but it's nice to see a (75%) formal proof.

Proof. Consider the residual graphs $G_f$ and $G_{f'}$ associated with flows $f$ and $f'$ before and after applying an augmentation through augmenting path $P$. The bottleneck edges in $P$ are present in $G_f$ but absent from $G_{f'}$ (as for each bottleneck edge $e \in P$, $e$ is saturated if it is a forward residual edge, or $e^R$ is emptied if $e$ is a backward residual edge). In addition, new edges which are anti-parallel to the bottleneck edges in $G_f$ are created in $G_{f'}$.

Let's assume there is only one bottleneck edge $(u, v) \in P$ and compare the distances of $u$ and $v$ in $G_f$ to their distances in $G_{f'}$. Denote the distance of a node $u$ in a particular residual graph $G_f$ as $d_f(u)$. Since $(u, v)$ is an edge in $P$, $d_f(v) = d_f(u) + 1$. What can we say about the distances of $u$ and $v$ in $G_{f'}$? Since $(u, v)$ is a bottleneck edge, it is absent from $G_{f'}$. Note that the distance to $v$ can never decrease from one iteration to the next by removing edges pointing into $v$, and hence $d_{f'}(v) \geq d_f(v)$. What about the distance to $u$? Since $(u, v)$ is a bottleneck edge, it is replaced by an anti-parallel edge $(v, u)$ in $G_{f'}$. Is it possible that the distance to $u$ decreases because of a new edge pointing into it? The answer is no. To see why, suppose that the distance to $u$ does decrease from one iteration to the next; that is

$$$$d_f(u) > d_{f'}(u)$$$$

If the distance to $u$ decreases, it can only possibly decrease by using the edge $(v, u)$. Thus $d_{f'}(u) = d_{f'}(v) + 1$, and

$$$$d_{f'}(u) > d_{f'}(v)$$$$

Taking these two inequalities together, we have

$$$$d_f(u) > d_{f'}(v)$$$$

We have just argued that the distance to $v$ can never decrease. Hence

$$$$d_{f'}(v) \geq d_f(v)$$$$

Again, taking the two previous inequalities together, we have

$$$$d_f(u) \geq d_f(v)$$$$

But this contradicts the fact that $d_f(v) = d_f(u) + 1$. Therefore, the distance to $u$ cannot decrease from one iteration to the next.

We can repeatedly apply the same argument for the case when there are many bottleneck edges. Just consider edges in $P$ in increasing order of their nodes' distance from the source and proceed by induction.

Claim. Prove this part more rigorously.

From this, we can conclude that $d_{f'}(v) \geq d_f(v)$ for all nodes $v$ and for all augmentation steps $f' = Augment(f, P)$.

In particular, the distance from the source to the sink never decreases from one iteration to the next.

Corollary 8. (Monotonically Non-Decreasing Augmenting Path Lengths) Throughout the shortest augmenting paths algorithm, the length of an augmenting path in the residual graph never decreases from one iteration to the next. That is, for all augmentation steps $f' = Augment(f, P)$, $$d_{f'}(t) \geq d_f(t)$$

Armed with Lemma 7, we can now prove the following.

Lemma 9. (Using Reverse Edges Increases Augmenting Path Length) Suppose that at some iteration $i$ of the algorithm, $(u, v)$ is a bottleneck edge in the augmenting path $P$. At some later iteration $i' > i$, the residual edge $(v, u)$ may be in the residual graph. At that point, if the augmenting path $P'$ includes $(v, u)$, then the length of $P'$ is strictly greater than the length of $P$.

Again, you can convince yourself by observing the augmenting paths found by the algorithm on several different graphs, but let's see a (75%) formal proof.

Proof. There may be many bottleneck edges in $P$, but as before, we can first assume there is only one and later generalize by induction. Call this bottleneck edge $(u, v)$. Let $f$ and $f'$ denote the flows (before applying the augmentation) at the earlier and the later iteration respectively. Note that if $(v, u)$ does not exist in $G_{f'}$ then this discussion is moot. So let's assume that it exists. If the shortest path $P'$ goes through $(v, u)$, then

$$$$d_{f'}(u) = d_{f'}(v) + 1 > d_{f'}(v)$$$$

We know from Lemma 7 that

$$$$d_{f'}(v) \geq d_f(v)$$$$

Since $(u, v)$ is an edge in $P$,

$$$$d_f(v) = d_f(u) + 1 > d_f(u)$$$$

Putting these three inequalities together, we conclude that $d_{f'}(u) > d_f(u)$. Note that this is a stronger statement than Lemma 7 implies, since here we have a strict inequality. From here, it is not hard to conclude that the distances to all nodes $w$ in the path from $u$ to $t$ are strictly larger in $G_{f'}$ than in $G_f$. More briefly, $d_{f'}(w) > d_f(w)$. In particular, $d_{f'}(t) > d_f(t)$. All of this assumes we included the reverse edge $(v, u)$ in $P'$.

How many times can we avoid using the reverse of a bottleneck edge before we are forced to use one to find an augmenting path? We have $O(E)$ possible bottleneck edges to exhaust before we are forced to use the reverse of any one of them. Therefore, the shortest augmenting path must strictly increase after $O(E)$ iterations.

Corollary 10. (Bound on How Long the Augmenting Path Length Remains Constant) The length of the shortest augmenting path increases after at most $O(E)$ iterations.

Using the above facts, it is not that hard to prove the following theorem.

Theorem 11. (Efficiency of Shortest Augmenting Paths) The shortest augmenting paths algorithm solves the maximum flow problem in $O(E^2V)$ time.

Exercise. Prove Theorem 11. (Hint: How many times can the length of the shortest augmenting path increase?) See I.53 for the answer.

Problem. In the proof of Lemma 9 above, we did not care whether or not the bottleneck edge $(u, v)$ reappears in the residual graph between iterations $i$ and $i'$, since we know that if it does reappear in iteration $i^\star < i'$, then $(v, u)$ had to be a bottleneck edge of some augmenting path for some other intermediate iteration $i^* < i^\star$. In any case, the augmenting path at iteration $i'$ is still longer than the augmenting path at iteration $i$, since $d_{i'}(t) \geq d_{i^\star}(t) \geq d_{i^*}(t) > d_i(t)$. In addition though, we also know that $d_{i^\star}(u) > d_i(u)$. This means that whenever $(u, v)$ appears as a bottleneck edge in the residual graph, the distance to $u$ strictly increases. Using bounds on the number of times the distance to a node can increase, give an alternative proof of the efficiency of the shortest augmenting paths algorithm.

See I.48-I.53 for another, slightly different proof.

Ford and Fulkerson did not really specify what method must be used to find augmenting paths. We can think of the Ford-Fulkerson algorithm as not really an algorithm, but more of a template, where the actual method for finding the paths can be plugged in to create a full-fledged algorithm. Ford and Fulkerson's contribution was simply to establish the paradigm of “successively find augmenting paths,” and left it to future generations of computer scientists to extend and refine this paradigm. The Edmonds-Karp improvement plugs in the “Shortest Augmenting Paths” method into this template. Although Edmonds-Karp is significantly better than vanilla Ford-Fulkerson, it is still quite bad, requiring $\Omega(V^5)$ in dense graphs. We need faster improvements. This and the rest of the algorithms in this section, except for the last, are merely different variations on how to find the augmenting paths, with different time complexities, but the basic idea is the same. (Hence, correctness of each of these easily follows from the correctness of Ford-Fulkerson.) In practice, however, the most efficient max-flow algorithms today use a completely different approach (cue dramatic pondering on the nature of scientific progress): the pre-flow push-relabel approach, which we will see in the last part of this section. But first, let's develop our intuition using simple algorithms before diving into the more complicated approach.

### Finding Augmenting Paths Smartly: Fattest Augmenting Paths (Edmonds-Karp)

In the same paper where Edmonds and Karp introduce their algorithm above, they also describe another intuitive way to improve the Ford-Fulkerson algorithm: take augmenting paths with the largest bottleneck capacity, the fattest augmenting paths. This makes sense because increasing the flow by as much as possible per iteration leads to lessening the number of iterations of augmentation required. We can do this using some simple modification of Prim's/Dijkstra's algorithm. It can be shown that this method requires $O(E \lg (EC))$ augmentations in total, and therefore $O(E^2 \lg V \lg (EC))$ total time, though we do not prove it here. This looks like an improvement over the shortest augmenting paths method. However, on dense graphs, the logarithmic terms and the constant factor overhead of using a priority queue for Prim's/Dijkstra's become significant. Doing Prim's/Dijkstra's without a priority queue turns out to not help either even with dense graphs. Compared with the shortest augmenting paths method, for most problems, the slight improvement in the sparse graph case only is not worth the extra implementation effort.

### Finding Augmenting Paths Smartly: Capacity-Scaling (Gabow)

A slightly different idea for improving the Ford-Fulkerson algorithm was proposed by Gabow in 1985: maintain a scaling parameter $\Delta$ and consider only residual edges whose capacities are at least $\Delta$. This $\Delta$ is initialized to be the largest power of two smaller than the maximum capacity of any edge going out of the source. A phase of several augmentations using this fixed $\Delta$ is performed, until no more augmentations can be made, and then $\Delta$ is divided by $2$. This process is repeated until $\Delta$ reaches $0$. See I.42 for pseudocode. This algorithm runs in $O(E^2 \lg C)$ time. We will skip the proof. You can look at I.44-I.45 for it. We will also skip the implementation. It is not too hard to try it on your own. In practice, this algorithm is significantly better than the shortest augmenting paths algorithm for sparse graphs, but only marginally better for dense graphs. Be forewarned though, that an implementation of capacity-scaling using DFS performs significantly more poorly than one that uses BFS.

### Finding Augmenting Paths Smartly: Level Graph Blocking Flows (Dinitz)

The previous two improvements we have seen are theoretically interesting, but they are not significantly better than the shortest augmenting paths algorithm to be worth using. This one is though. Dinitz invented it in 1970, and proved independently of Edmonds and Karp that the max-flow problem can be solved in polynomial time. Interestingly, this algorithm is more commonly known today as “Dinic's” algorithm, because the guy who gave the initial lectures about this algorithm kept mispronouncing Dinitz' name.

The idea behind the algorithm is not that difficult. Like Edmonds and Karp's algorithm, Dinic's algorithm will find the shortest augmenting paths, but it will find all augmenting paths of a fixed length in one go. We previously discussed two natural strategies for improving the running time of augmenting path algorithms: find paths efficiently, and reducing the number of iterations of augmentation. They are not mutually exclusive. Dinic's algorithm does both. By simultaneously augmenting along all shortest paths with the same length, Dinic's algorithm will require only $O(V)$ phases of augmentation. (Why?) Using the idea of a level graphs and blocking flows, Dinic's algorithm can find and augment along all paths with the same length in $O(VE)$. This makes the total running time $O(V^2E)$, which is a significant improvement over Edmonds and Karp's $O(VE^2)$ for dense graphs, and which in practice happens to also work significantly better than Edmonds-Karp in general for graphs of different densities. Let's make this intuition more formal.

First, we need the concept of a level graph. The level graph of a given graph $G = (V, E)$ is the subgraph containing only edges that can possibly be part of a shortest path from the source $s$ to the sink $t$. Specifically, denote $d(v)$ as the distance of a node $v$ from $s$, that is, the number of edges in the shortest path from $s$ to $v$. The level graph $L(G) = (V, E_L)$ contains only those edges $(u, v) \in E$ where $d(v) = d(u) + 1$. See I.49 for an example. Note that for some residual graph $G_f$, a shortest augmenting path only contains edges in $L(G_f)$.

The level graph is closely related to the BFS tree.

Next, let's introduce the idea of a blocking flow. A flow $f$ is a blocking flow for flow network $G$ if there are no $s \sim t$ paths in the subgraph obtained by removing saturated edges from $G$.

Exercise. Prove or disprove: every maximum flow is a blocking flow.

Exercise. Prove or disprove: every blocking flow is a maximum flow.

Exercise. Prove or disprove: If $f$ is a blocking flow for $G$, then there are no augmenting paths in $G_f$.

Stated another way, a blocking flow is just a flow which prevents augmentation using only forward residual edges. Notice that our first algorithm was simply: find and augment along $s \sim t$ paths until the current flow is a blocking flow.

Each blocking flow can represent the flow produced by a bunch of augmenting paths. Dinic's algorithm will repeatedly find blocking flows and update the global flow using these blocking flows instead of individual augmenting paths. Let's make this notion of “augmenting a flow with another flow” more formal. Let $f$ and $b$ be two flows on $G$. Define the augmentation of $f$ by $b$ (or more simply, just the sum of $f$ and $b$) as flow produced by combining the two flows for each edge: $f' = f + b$ iff $f'(e) = f(e) + b(e)$ for all $e \in G$.

At a very high level, Dinic's algorithm can be described as follows. Denote the flow at iteration $i$ as $f_i$. Let $f_0$ initially be an empty flow. Perform $O(V)$ phases of augmentation. In each phase, do the following:

1. Construct the level graph $L(G_{f_i})$ of the residual graph $G_{f_i}$.
2. Compute a blocking flow $b_i$ of $L(G_{f_i})$.
3. Update the flow by augmenting it with the blocking flow: let $f_{i+1} = f_i + b_i$.

This description does not look intuitive at all. Weren't we trying to find all augmenting paths with the same length all in one phase? Why these notions of level graph and blocking flow? The reason why “find all augmenting paths with the same length” is the same as “find a blocking flow in the level graph” is made clear by the following lemma.

Lemma 12. (Augmentation by Level Graph Blocking Flow Increases Augmenting Path Length) Let $f$ be a flow and $b$ be a blocking flow in $L(G_f)$. The distance from the source to the sink is strictly greater in $G_{f+b}$ than in $G_f$: $$d_{f+b}(t) > d_f(t)$$

Problem. Prove Lemma 12. (Hint: Consider Lemma 9.)

If you understand the proofs for the efficiency of Edmonds-Karp algorithm and the concepts above, it is actually not impossible to complete with Dinic's algorithm on your own. All you need is to find a way to perform each phase of augmentation in $O(VE)$ time.

Exercise. Attempt to complete Dinic's algorithm on your own. (Hints: For a single phase, how much time is needed to construct the level graph? At most how many individual augmenting paths can make up a blocking flow of the level graph? Using the level graph, can we find one such augmenting path in $O(V)$? What if we allow the level graph to be modified every time we augment along a path? In particular, what if we can delete nodes and edges from the level graph?)

Did you figure it out? It is easy to perform steps 1 and 3 of each phase both in $O(E)$ time. Step 2 is trickier. Simply performing a DFS/BFS to find individual augmenting paths in the level graph to compute the blocking flow still requires $O(E)$ per path. By Corollary 10, this makes each phase require $O(E^2)$ time. This is really just Edmonds-Karp stated in an unnecessarily fancier way. However, if we can somehow find individual augmenting paths in the level graph in $O(V)$ time, then we are done. DFS happens to help us in this case. Let's assume that we get lucky, and picking the first outgoing edge in every DFS call leads us to the sink. Then, we can find one augmenting path (plus update the blocking flow and delete bottleneck edges from the level graph) in $O(V)$. The problem is, we can be unlucky in the DFS, and reach a dead end, say $v$, that has no path to the sink, causing us to backtrack and to require $O(E)$ time to find one augmenting path. In this case, however, we are sure that no augmenting paths will ever pass through $v$ until the next phase, so we can delete $v$ (and all edges incident to it) from the level graph before backtracking. Since there are only $V$ nodes in the graph, this unlucky case will only happen $O(V)$ times. We're done.

See I.56-I.69 for illustrations, pseudocode, and a more detailed proof.

Exercise. Before looking at the implementation of Dinic's algorithm below, re-solve UVa 820 - Internet Bandwidth, this time using your own implementation of Dinic's algorithm. Compare the actual running times of Edmonds-Karp's and Dinic's algorithms for this problem. Some care is needed to ensure that deleting a node or edge from the level graph can actually be done in constant time, to ensure the overall running time of the algorithm is $O(V^2E)$.

Here is a clean implementation of Dinic's algorithm.

#include <bits/stdc++.h>
#define MAX_N 100
#define INF 1'000'000
using namespace std;
int n, m, s, t;
unordered_set<int> L_adj_rev[MAX_N+1]; // to avoid extra linear factor for node deletion
int c[MAX_N+1][MAX_N+1];
int f[MAX_N+1][MAX_N+1];
int d[MAX_N+1]; // distance for level graph
int p[MAX_N+1]; // parent for blocking flow

bool make_level_graph() {
memset(d, -1, sizeof d);
d[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
if(c[u][v] - f[u][v] > 0) {
if(d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
if(d[v] == d[u] + 1) {
}
}
}
}
return d[t] != -1;
}

bool dfs(int u) {
if(u == t) return true;
if(dfs(v)) {
p[v] = u;
return true;
}
}
// node $u$ has no path to the sink, delete it from level graph
}
return false;
}

bool find_aug_path() {
memset(p, -1, sizeof p);
p[s] = 0;
return dfs(s);
}

int main() {
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cin >> n >> s >> t >> m;
for(int i = 0; i < m; i++) {
int u, v, capacity;
cin >> u >> v >> capacity;
c[u][v] += capacity;
}
int max_flow_value = 0;
while(make_level_graph()) {
while(find_aug_path()) {
int b = INF;
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) b = min(b, c[u][v] - f[u][v]);
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) {
if(c[u][v] - f[u][v] == b) { // delete bottleneck edges from the level graph
}
f[u][v] += b, f[v][u] -= b;
}
max_flow_value += b;
}
}
cout << max_flow_value << endl;
return 0;
}


Unfortunately, if you try using this implementation to solve UVa 820 - Internet Bandwidth, you will get TLE. Explicitly maintaining a level graph significantly degrades the running time. Instead, let's try to retrieve the level graph implicitly using only the distance information for each node. Implementing this properly is not trivial, and a buggy implementation can very easily make the running time degenerate to $O(VE^2)$.

The idea for the implementation is, when we run DFS, we use the original adjacency list to get the neighbors of a node. However, to ensure that a neighbor $v$ is actually a neighbor of $u$ in the current level graph, we need to check three things.

1. The distances are correct, namely: $d_v = d_u + 1$.
2. We haven't yet deleted the edge $e = (u, v)$ from the level graph in a previous augmentation step. In other words, $c(e) - f(e) > 0$.
3. We haven't yet deleted node $v$ from the level graph. We can delete a node by marking its distance to be some dummy value like -1, so that the first condition subsumes this one.

We ignore $v$ if it fails to satisfy any of these three properties.

In addition to checking these conditions, we have to ensure that we don't repeatedly visit some edge or node that no longer exists in the level graph. Otherwise, all iterations of DFS will degenerate to $O(E)$, causing the entire algorithm to degenerate to $O(VE^2)$. Observe that once we discover a neighbor $v$ that we should ignore, we should continue to ignore it for the rest of the augmentation phase. We can therefore maintain for each node $u$ a pointer to its first neighbor that still satisfies the three conditions above. Initially, this pointer points to its first neighbor in the original adjacency list. Starting from node $u$, if we are in a lucky case, its neighbor $v$ satisfies the three conditions above, and the DFS from its neighbor $v$ succeeds. Otherwise, we are in an unlucky case. In this case, the neighbor $v$ will never be a valid neighbor of $u$ in the level graph until the end of the current augmentation phase, so we move the pointer of $u$ to its next neighbor. This effectively deletes $(u, v)$ from the level graph and helps us avoid repeated visits. Carefully read the code below for the details, and convince yourself that this implementation is $O(V^2E)$.

#include <bits/stdc++.h>
#define MAX_N 100
#define INF 1'000'000
using namespace std;
int n, m, s, t;
vector<int> adj[MAX_N+1]; // revert to adj list to make it easy to keep track of ignored neighbors
int adj_ptr[MAX_N+1]; // the index of the first neighbor of a node which is not yet ignored
int c[MAX_N+1][MAX_N+1];
int f[MAX_N+1][MAX_N+1];
int d[MAX_N+1]; // distance for level graph
int p[MAX_N+1]; // parent for blocking flow
bool make_level_graph() {
memset(d, -1, sizeof d);
d[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
if(c[u][v] - f[u][v] > 0 && d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[t] != -1;
}

bool dfs(int u) {
if(u == t) return true;
if(d[v] == d[u] + 1 && c[u][v] - f[u][v] > 0 && dfs(v)) {
// lucky case: we immediately return, and adj_ptr[u] remains untouched
p[v] = u;
return true;
}
// Unlucky case: Either edge $(u, v)$ or node $v$ doesn't exist in the level graph.
// Moving to the next neighbor increments adj_ptr[u] along with $i$,
// because we assigned $i$ by reference.
// This effectively removes $v$ from the level graph neighbor list of $u$
// until the end of the current phase.
}
// node $u$ has no path to the sink, "delete" it from level graph
d[u] = -1;
return false;
}

bool find_aug_path() {
memset(p, -1, sizeof p);
p[s] = 0;
return dfs(s);
}

int main() {
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cin >> n >> s >> t >> m;
for(int i = 0; i < m; i++) {
int u, v, capacity;
cin >> u >> v >> capacity;
// adj list will have duplicates, but this doesn't hurt running time too much
// BFS for making the level graph will still be $O(E)$
c[u][v] += capacity;
}

int max_flow_value = 0;
while(make_level_graph()) {
// with each new phase, the first non-ignored neighbor is
// its first neighbor in the original adjacency list
while(find_aug_path()) {
int b = INF;
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) b = min(b, c[u][v] - f[u][v]);
for(int v = t, u = p[v]; v != s; v = u, u = p[v]) f[u][v] += b, f[v][u] -= b;
max_flow_value += b;
}
}
cout << max_flow_value << endl;
return 0;
}


Interestingly, using a data structure called a link-cut tree (invented by Sleator and Tarjan in 1982), the time required to find a blocking flow in the level graph can be reduced from $O(VE)$ to $O(E \lg V)$, making the total time $O(VE \lg V)$. With some additional techniques and data structures, each blocking flow can be found in $O(E \lg (V^2/E))$, making the total time $O(VE \lg (V^2/E))$. These is quite close to the best bounds for the max-flow problem known today. However, because the data structures are quite complicated and the constant factors in the running time are quite large, this is not used in practice. The best bounds are $O(VE)$, due to an algorithm made by Orlin in 2013. (Note how recent it is! Research on network flows is still very active.) But that algorithm is extremely complicated and impractical today. Let's now turn our attention to an algorithm of moderate difficulty to understand, and which works very well in practice.

### Push-Relabel Approach to the Maximum Flow Problem

A radically different approach to the max flow problem was introduced by Goldberg and Tarjan in 1988, called the push-relabel approach. Similar to the Ford-Fulkerson algorithm, the basic skeleton of the approach is not an algorithm itself. There is a part which needs to be specified in full, and the overall algorithm can easily be improved by simple tweaks to this part. Since then, a number of different approaches with strictly better asymptotic complexities have been invented, but they have not been proven to be more efficient in practice than push-relabel algorithms. Hence, push-relabel algorithms are still the gold standard for maximum flow. Similar to our discussion of the augmenting paths method, we will first describe and implement the simplest version, and add the improvements later.

### Practice Problems

Before moving on to the next section, I recommend practicing what you just learned with the following problems first (submission is not required for these problems):

Try to use all three algorithms (shortest augmenting paths, blocking flow, and pre-flow push-relabel) to solve each problem.

## Bipartite Matching and Hall's Marriage Theorem

### Reduction to Maximum Flow

At first glance, bipartite matching and maximum flow appear to be completely different problems. However, there is a very simple reduction from the former to the latter.

### Analysis of Maximum Flow Algorithms on Unit-Capacity Simple Networks

(This section is under construction)

### Alternating Chains (Kuhn) and Berge's Lemma

(This section is under construction)

### Multiple Alternating Chains (Hopcroft-Karp)

(This section is under construction)

### Practice Problems

Before moving on to the next section, I recommend practicing what you just learned with the following problems first (submission is not required for these problems):

## Disjoint Paths and Menger's Theorem

(This section is under construction)

## Special Cases of NP Complete Problems Reduced to Bipartite Matching

(This section is under construction)

## Minimum Cost Flows

(This section is under construction)

Next