0
$\begingroup$

The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.

The notation $\delta(u, v)$ is used to denote shortest-path from $u$ to $v$.


lemma proof1 proof2


Question 1:

Because of how we chose $v$, we know that the distance of vertex $u$ from the source $s$ did not decrease, i.e., $\delta_{f'}(s, u) \geq \delta_{f}(s, u)$

Why the shortest-path from $s$ to $u$ after the augmentation of flow $f$ must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge $(u, v)$. But, the vertex $u$ still in place, isn't it must be strictly equal ?

Question 2:

If we had $(u, v) \in E_f$, then we would also have $\delta_f(s,v) \leq \delta_f(s, u) + 1$

This looks like ok for me to have such case. We claim that distance from $s$ to $v$ is less than or equal to the distance from $s$ to $u$ plus 1. But in the graph before the first augmentation this case must be true. It is false for less than case, but true for equal case.

Question 3:

How can we have $(u, v) \notin E_f$ and $(u, v) \in E_{f'}$ ? The augmentation must have increased the flow from $v$ to $u$. The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from $s$ to $u$ in $G_f$ has $(v, u)$ as its last edge.

The edge set $E_f$ is before the first augmentation and $E_{f'}$ is after it. The first augmentation must remove the edge $(u, v)$ and put the reverse edge $(v, u)$ into the edge set $E_{f'}$, but not the same edge $(u, v)$. That is why how we can have $(u, v)$ in $E_{f'}$ ?

$\endgroup$
  • $\begingroup$ Q1: The distance from $s$ to $u$ could increase because the just-added flow $f$ "completely used up" some edge(s) in the residual graph that were on the only shortest path between $s$ and $u$. If this didn't happen, then the distance will remain unchanged. We don't know which happened; all we do know is that this distance could not have decreased, because in that case we would have picked $u$ instead of $v$ in the first place. So the strongest thing we can say with certainty is that the distance from $s$ to $u$ has stayed the same or increased. $\endgroup$ – j_random_hacker Apr 29 at 0:05
  • $\begingroup$ @j_random_hacker Ok. But as I understand from the proof description, the first thing to consider is this augmentation is the first one. From the statement "because of how we chose v", the edge u -> v is a bottleneck. That is why we completely use up (u, v) edge's capacity and add the reverse edge (v, u). How it is possible by removing the edge (u, v) to block the path from s to u ? $\endgroup$ – maksadbek May 8 at 16:15
  • $\begingroup$ It's not the first augmentation, but the first augmentation in which some distance from s decreased. I don't know what you mean by "bottleneck". "How it is possible by removing the edge (u, v) to block the path from s to v?" -- (1) I don't understand how that is connected to anything; (2) in any case, consider the case where s=u and uv is the only edge in the graph. $\endgroup$ – j_random_hacker May 8 at 17:01

Your Answer

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

Browse other questions tagged or ask your own question.