2
$\begingroup$

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.

This is what is written on the slides I am reading:

Theorem. [Even–Tarjan 1975] In simple unit-capacity networks, Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.

Pf.

・Lemma 1. Each phase of normal augmentations takes $O(m)$ time.

・Lemma 2. After $\sqrt{n}$ phases, $val( f ) ≥ val( f *) – \sqrt{n}$.

・Lemma 3. After $≤ \sqrt{n}$ additional augmentations, flow is optimal.

I think I get the first lemma: normal augmentation phase takes up to $O(m)$ because this is the cost of generating a level graph $L_G$. However, I have not understood what exactly happens after the "normal" augmentation (in what does the "special" augmentation phase consist? How many "phases" are needed?)

I have no clue about how the values in the other two lemmas are brought up. Could someone help me understand it?

Here are the slides I am referring to, in particular the ones between 92-96

Thanks a lot

$\endgroup$
6
  • $\begingroup$ Do you understand what $f^*$ is and that if your level graph has $\sqrt n$ many levels, then there is a level with at most $\sqrt n$ many vertices? Do you understand why the defined cut then has capacity at most $\sqrt n$? $\endgroup$
    – Pål GD
    Nov 6, 2023 at 18:57
  • $\begingroup$ $f*$ should be the maximum flow, while $f$ is the one in the current phase, I think. I don't understand what guarantees me that the definined graph will have $\sqrt{n}$ levels, but if I assume it does, than it makes sense that one level has less than $\sqrt{n}$ verticies. $\endgroup$ Nov 6, 2023 at 19:10
  • $\begingroup$ Then I would look at the statement "after $\sqrt n$ iterations, the length of the shortest augmenting path is at least $\sqrt n$. Can you make sense of it? $\endgroup$
    – Pål GD
    Nov 6, 2023 at 19:20
  • $\begingroup$ It's not clear to me what happens after an iteration. I understand what happens until slide 91, then the first iteration stops. How does the second one start? Does the level graph get recreated and how will it be different than before? I think this is why I don't understand your last sentence: after $\sqrt{n}$ iterations, the length of the shortest augmenting path is at least $\sqrt{n}$. I understand that there will be a level h with up to $\sqrt{n}$ verticies, and a level h+1 with more than $\sqrt{n}$ verticies. But I don't get why the number of iterations has to be $\sqrt{n}$. $\endgroup$ Nov 6, 2023 at 19:45
  • $\begingroup$ Maybe I am confusing phase and iterations. However, I am pretty lost. Thank you really a lot for your time and patience. $\endgroup$ Nov 6, 2023 at 19:47

1 Answer 1

1
$\begingroup$

I have no clue about how the values in the other two lemmas are brought up.

The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is chosen in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have at least $\sqrt n$ many layers, which means that there is a layer with at most $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L_i^\leftarrow$ be the set of vertices in $L_i$ with exactly one in-edge, and let $L_i^\rightarrow$ be all other vertices in $L_i$ (they all have exactly one out-edge since $G$ is a unit-capacity network). Notice that $L_i^\leftarrow, L_i^\rightarrow$ partitions $L_i$.

Now, let $A$ be the set of vertices in layers $L_j$ for $j < i$, plus $L_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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