2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Jan 4 '17 at 18:43
1
$\begingroup$

"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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.