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
1
$\begingroup$

Answer to Question 1:

Because of how we chose ๐‘ฃ, we know that the distance of vertex ๐‘ข from the source ๐‘  did not decrease, i.e., ๐›ฟ๐‘“โ€ฒ(๐‘ ,๐‘ข)โ‰ฅ๐›ฟ๐‘“(๐‘ ,๐‘ข)

Why the shortest-path from ๐‘  to ๐‘ข after the augmentation of flow ๐‘“ 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 (๐‘ข,๐‘ฃ). But, the vertex ๐‘ข still in place, isn't it must be strictly equal ?

Because in the Proof, "We will suppose that for some vertex $v \in V - \left \{ s, t\right \}$, there is a flow augmentation that causes the shortest-path distance from $s$ to $v$ to decrease". So, if we consider $u$ is the opposite type compared to $v$, that is to say, the shortest-path distance from $s$ to $u$ does not decrease: equation (26.13) $\delta _{f'}\left ( s,u \right )\geq \delta _{f}\left ( s,u \right )$ holds.

Of course, if you suppose that $u$ is same type as $v$, which has decreasing shortest-path distance from $s$ to $u$, then we can take $u$ to replace the $v$, and find the path, $p:s\rightarrow x \rightarrow u$, where $\delta _{f'}\left ( s,x \right )\geq \delta _{f}\left ( s,x \right )$ holds. In this case $x$ takes the place of $u$ in eq(26.13).

Answer to Question 2:

If we had (๐‘ข,๐‘ฃ)โˆˆ๐ธ๐‘“, then we would also have ๐›ฟ๐‘“(๐‘ ,๐‘ฃ)โ‰ค๐›ฟ๐‘“(๐‘ ,๐‘ข)+1

This looks like ok for me to have such case. We claim that distance from ๐‘  to ๐‘ฃ is less than or equal to the distance from ๐‘  to ๐‘ข 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.

If the shortest path from $s$ to $v$, $p_v: s\rightarrow u \rightarrow v$ overlaps with the shortest path from $s$ to $u$, $p_u: s\rightarrow u$, the equal case happens. $\delta_f(s,v)=\delta_f(s,u)+1$.

If the two paths $p_v$ and $p_u$ are not overlapped, the shortest path from $s$ to $v$, $p_v: s \rightarrow v$ would not contain the node $u$. Since $p_v$ is the shortest path, obviously the length of $p_v$ should be shorter than the length of $p_u$ + $(u,v)$ (another path from $s$ to $v$). Therefore the less than case happens: $\delta_f(s,v)<\delta_f(s,u)+1$.

Answer to Question 3:

How can we have (๐‘ข,๐‘ฃ)โˆ‰๐ธ๐‘“ and (๐‘ข,๐‘ฃ)โˆˆ๐ธ๐‘“โ€ฒ ? The augmentation must have increased the flow from ๐‘ฃ to ๐‘ข. The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from ๐‘  to ๐‘ข in ๐บ๐‘“ has (๐‘ฃ,๐‘ข) as its last edge.

The edge set $๐ธ_๐‘“$ is before the first augmentation and $๐ธ_{๐‘“โ€ฒ}$ is after it. The first augmentation must remove the edge (๐‘ข,๐‘ฃ) and put the reverse edge (๐‘ฃ,๐‘ข) into the edge set $๐ธ_{๐‘“โ€ฒ}$, but not the same edge (๐‘ข,๐‘ฃ). That is why how we can have (๐‘ข,๐‘ฃ) in $๐ธ_{๐‘“โ€ฒ}$ ?

$(u,v)\notin E_f$ and $(u,v)\in E_{f'}$ mean that the newly augmentation augments flow (a cancellation flow for $(u,v)$) along the edge $(v, u)$. Recall that, augmentation happens on the shortest path, which means that $(v,u)$ is on the shortest path $p$ from $s \leadsto v \rightarrow u \leadsto t$. If $p$ overlaps with the shortest path from $s \leadsto u$, $\delta _{f}\left ( s,v \right ) = \delta _{f}\left ( s,u \right )-1$ holds. However I am not sure now that the overlapping does happen.

$\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.