Do not understand a lemma regarding dinics algorithm

Question

Here you can find the following lemma with its proof.

Lemma: In a network with unit edge capacities, Dinitz algorithm terminates after $O(\sqrt{m})$ blocking flow computations.

Proof: Consider the layered network after $\sqrt{m}$ iterations. It has at most m edges. The average number of edges between any two layers is $\frac{m}{\sqrt{m}} = \sqrt{m}$. Hence, there must be at least one layer $i$ with at most $\sqrt{m}$ edges. Now consider the cut $S=\{v | level_f(v) < i\}$. It has capacity at most $\sqrt{m}$. Since each blocking flow augmentation increases flow by at least one, after $\sqrt{m}$ additional blocking flow augmentations, a maximum flow has been found. Hence, no more than 2$\sqrt{m}$ = $O(\sqrt{m})$ blocking flow augmentations are needed.

I don't understand the proof. The layered graph $G_{L}$ has m edges. But how does it look like after $\sqrt{m}$ iterations? Is the average number of edges of $G_{L}$ between any two layers $\frac{m}{\sqrt{m}} = \sqrt{m}$ after $\sqrt{m}$ iterations? And the confusion continuous with the set $S$.

Could someone unfold this proof for better understanding?

Answer 1

"How does it look like after $\sqrt{m}$ iterations?"

To see this, we need a property: the number of layers increases by at least $1$ after each iteration. In other word, the shortest distance from $s$ (source) to $t$ (sink) increases by at least $1$. This is the key property of Dinic's algorithm. I'll put the proof at the end. (Please help if anyone has a better way to arrange these contents. I don't want to let the proof occupy too much space.)

So after $\sqrt{m}-1$ iterations, $G_L$ has at least $\sqrt{m}+1$ layers, because there are at least $2$ layers at first, one for $s$ and one for $t$. This means there are at least $\sqrt{m}$ "edge layers" between the vertex layers. So the edge layer with the least number of edges has at most $\frac{m}{\sqrt{m}}=\sqrt{m}$ edges. One more thing you should notice is this edge layer forms a $s$-$t$ cut in the residual graph with capacity at most $\sqrt{m}$. (You can't jump across any layer, so you must pass this layer.) According to max-flow-min-cut theorem, capacity of maximum flow in the residual graph is at most $\sqrt{m}$. So we need at most $\sqrt{m}$ more iterations. In conclusion, the total number of iterations is $O(\sqrt{m})$.

Proof of the key property:

Suppose at some iteration we have residual network $G_f$ and its corresponding level graph $G_L$, and after one iteration we have residual network $G_f'$. To prove that $s$-$t$ distance in $G'_f$ is longer, first let's see the difference between $G_f$ and $G_f'$: if an edge $(u,v)$ is saturated, $(u,v)$ is removed and $(v,u)$ is added. Note that the blocking flow only contains edge in $G_L$, so $(u,v)$ is a "foward" edge in $G_L$, and $(v,u)$ is a "backward" edge in $G_L$. Here "forward" means the edge moves from lower level to higher level in the level graph.

Consider a shortest path from $s$ to $t$. Each edge $e$ on this path has three possibilities:

1. $e\notin G_f$. In this case $e$ is new, so it's "backward" in $G_L$ according to our claim above.

2. $e\in G_f$ but $e\notin G_L$. In this case, $e$ can't be forward. Otherwise it would be contained in $G_L$. (Note that a forward edge can't jump across a layer because the level graph is constructed based on shortest distance.)

3. $e\in G_L$. This is the only possible forward edge, which increases the level by exactly $1$.

Consider the level in $G_L$ of each vertex on the $s$-$t$ path. The level increases by at most $1$ after each step. So the shortest path from $s$ to $t$ in $G_f'$ is never shorter than the shortest path in $G_L$. Furthermore, it should be strictly longer: if the distance is the same, it means the shortest path in $G_f'$ only consists of type $3$ edges. This means we can find an unsaturated path in $G_L$, which violates the definition of blocking flow.

Therefore, the number of layers is strictly increasing.