1
$\begingroup$

I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path theorem. Now the theorem which is the subject of this question depends on two other theorems so I present the dependence before presenting the actual theorem and the difficulty which I face in the said.


Dependencies:

Theorem 22.7 (Parenthesis theorem) In any depth-first search of a (directed or undirected) graph $G = (V, E)$, for any two vertices $u$ and $v$;, exactly one of the following three conditions holds:

  • the intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ are entirely disjoint, and neither $u$ nor $v$ is a descendant of the other in the depth-first forest,

  • the interval $[d[u], f[u]]$ is contained entirely within the interval $[d[v], f[v]]$, and $u$ is a descendant of $v$; in a depth-first tree,

  • the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$, and $v$ is a descendant of $u$ in a depth-first tree.

Corollary 22.8 (Nesting of descendants' intervals) Vertex $v$ is a proper descendant of vertex $u$ in the depth-first forest for a (directed or undirected) graph $G$ if and only if $d[u] < d[v] < f[v] < f[u]$.


Theorem 22.9 (White-path theorem)

In a depth-first forest of a (directed or undirected) graph $G = (V, E)$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $d[u]$ that the search discovers $u$, vertex $v$ can be reached from $u$ along a path consisting entirely of white vertices.

Proof

$\Rightarrow$ : Assume that $v$ is a descendant of $u$. Let $w$ be any vertex on the path between $u$ and $v$ in the depth-first tree, so that $w$ is a descendant of $u$. By Corollary 22.8, $d[u] < d[w]$, and so $w$ is white at time d[u].

$\Leftarrow$:

  1. Suppose that vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$, but $v$ does not become a descendant of $u$ in the depth-first tree.
  2. Without loss of generality, assume that every other vertex along the path becomes a descendant of $u$. (Otherwise, let $v$ be the closest vertex to $u$ along the path that doesn't become a descendant of $u$.)
  3. Let $w$ be the predecessor of $v$ in the path, so that $w$ is a descendant of $u$ ($w$ and $u$ may in fact be the same vertex) and, by Corollary 22.8, $f[w] \leq f[u]$.
  4. Note that $v$ must be discovered after $u$ is discovered, but before $w$ is finished.$^\dagger$ Therefore, $d[u] < d[v] < f[w] \leq f[u]$.
  5. Theorem 22.7 then implies that the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$.$^{\dagger\dagger}$
  6. By Corollary 22.8, $v$ must after all be a descendant of $u$. $^\ddagger$

$\dagger$ : Now it is clear that since $u$ is the first vertex to be discovered so any other vertex (including $v$) is discovered after it. In point $1$ we assume that $v$ does not become the decendent of $u$, but by the statement that but before $w$ is finished I feel that this is as a result of exploring the edge $(w,v)$ (this exploration makes $v$ ultimately the descendant of $u$, so the proof should have ended here $^\star$)

$\dagger\dagger$ : Considering the exact statement of theorem 22.7 , I do not get which fact leads to the implication in $5$.

$\ddagger$ : The proof should have ended in the $\star$, but why the stretch to this line $6$.

Definitely I am unable to get the meaning the proof of the $\Leftarrow$. I hope the authors are using proof by contradiction.

(I thought of an alternate inductive prove. Let vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$. We apply induction on the vertices in the white path. As a base case $u$ is an improper descendant of itself. Inductive hypothesis, let all vertices from $u$ to $w$ be descendants of $u$ , where $w$ is the predecessor of $v$ in the white path. We prove the inductive hypothesis by the exploration of the edge $(w,v)$. But I want to understand the proof the text.)

$\endgroup$
  • 1
    $\begingroup$ $\dagger\dagger$ Theorem 22.7 concludes that exactly one of the three conditions listed is satisfied. The inequalities listed in (4) show that the intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ intersect. Therefore, the first condition of the theorem is not the one being satisfied. In the other two conditions one of these two intervals is inside the other. Now, because the inequality $d[u]<d[v]$ is strict, it can't be that $[d[u],f[u]]$ is inside $[d[v],f[v]]$. So, the third condition in the theorem is the only one that can be satisfied. $\endgroup$ – plop Aug 5 at 17:02
  • 1
    $\begingroup$ $\dagger$ This is also using theorem 22.7 or its corollary. "d[u]<d[v]" is part of the assumption, that by time $d[u]$ the vertex $v$ is still white. "f[w]\leq f[u]" comes from Corollary 22.8, since $w$ is a descendant of $u$. The inequality $d[v]<f[w]$ is due to $(w,v)$ being an edge. Because all neighbors of $w$ must be discovered before we consider it finished. Now, the claim that the proof should end here is jumping to the conclusion of the theorem without justification. It hasn't been justified that DFS will actually use $(w,v)$ to discover $v$. $\endgroup$ – plop Aug 5 at 18:00
  • $\begingroup$ @plop could you please pin point to me as to in which part of the proof (and how) the proof justifies that DFS will actually use $(w,v)$. $\endgroup$ – Abhishek Ghosh Aug 5 at 18:33
  • 1
    $\begingroup$ The proof doesn't show that $(w,v)$ will be used. It can't, since that is not necessarily true. What it proves is that $v$ will be discovered following some path departing from $u$. $\endgroup$ – plop Aug 5 at 18:35
  • $\begingroup$ @plop since the proof can't show that $(w,v)$ shall be used ,that is the reason why I hope they are taking all the pains to (5) and (6) to mathematically (in a generalized sense) show that $v$ becomes a descendant of $u$ in the ultimate run as per the inequalities devised (which is strictly based on the working of $\text{DFS}$). The thing is that they did not say about the intuition which you shared with me. Thank you... $\endgroup$ – Abhishek Ghosh Aug 5 at 19:04
2
$\begingroup$

$\dagger\dagger$ Theorem 22.7 concludes that exactly one of the three conditions listed is satisfied. The inequalities listed in (4) show that the intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ intersect. Therefore, the first condition of the theorem is not the one being satisfied. In the other two conditions one of these two intervals is inside the other. Now, because the inequality $d[u]<d[v]$ is strict, it can't be that $[d[u],f[u]]$ is inside $[d[v],f[v]]$. So, the third condition in the theorem is the only one that can be satisfied.

$\dagger$ This is also using theorem 22.7 or its corollary. The inequality $d[u]<d[v]$ is part of the assumption, that by time $d[u]$ the vertex $v$ is still white. The inequality $f[w]\leq f[u]$ comes from Corollary 22.8, since $w$ is a descendant of $u$. The inequality $d[v]<f[w]$ is due to $(w,v)$ being an edge. Because all neighbors of $w$ must be discovered before we consider it finished. Now, the claim that the proof should end here is jumping to the conclusion of the theorem without justification. It hasn't been justified that DFS will actually use $(w,v)$ to discover $v$.

Example 1: For example, consider the graph with vertices $1,2,3,4$ and (directed) edges $(1,2),(1,4),(2,3),(4,3)$ and we start at $1$ doing DFS. Assume that we already discovered $1$ and $2$.

At this point the vertex $v=3$ is is a white path from $u=w=2$. Just one edge $(2,3)$. DFS will discover $3$ and make it a descendant of $2$. There is no way to change that, since Theorem 22.9 proves it. But imagine that at this point we stop obeying DFS and go to discover $4$ and from $4$ go and discover $3$. Then $3$ wouldn't be a descendant of $2$. It would only be a descendant of $4$ and $1$. Theorem 22.9 proves that DFS wouldn't do that.

Example 2: This is to illustrate the question in the comments. Consider the graph with vertices $1,2,3,4$ and edges $(1,2),(1,4),(2,3),(2,4),(3,4)$. Assume that we have discovered already $1$ and $2$, in that order. The vertex $v=4$ is in a white path from $u=w=2$. However, the edge $(2,4)$ doesn't necessarily need to be used by DFS. If the neighbors of a vertex are considered in the order according to the labels that we gave them in this example, then from $2$ DFS will discover $3$ and from $3$ it will discover $4$. Then $3$ becomes finished, then $2$ becomes finished, and $1$ becomes finished, in that order.

While theorem 22.9 doesn't ensure that either $(2,4)$ or $(3,4)$ will be used, since that depends on the other in which neighbors are explored, note that it does ensure that the edge $(1,4)$ will not be used (under the assumptions of the example that $1$ was discovered and $2$ just got discovered). In fact, Theorem 22.9 implies that $4$ will be a descendant of $2$.

| cite | improve this answer | |
$\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.