Question

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph \(G(V,E)\) as input, where \(d[v]\) and \(f[v]\) are the discovery time and finishing time, respectively, of the vertex \(v \in V\).

DFS(G):
  unmark all v in V
  t <- 0
  for each v in V
    if v is unmarked
      t <- Explore(G, v, t)
    end if
  end for

Explore(G, v, t):
  mark v
  t <- t + 1
  d[v] <- t
  for each (v, w) in E
    if w is unmarked
      t <- Explore(G, w, t)
    end if
  end for
  t <- t + 1
  f[v] <- t
  return t

Suppose that the input directed graph \(G(V,E)\) is a directed acyclic graph (DAG).
For an edge \((u,v) \in E\), which of the following options will NEVER be correct?

• A. \(d[u] < d[v] < f[v] < f[u]\)
• B. \(d[v] < d[u] < f[u] < f[v]\)
• C. \(d[v] < f[v] < d[u] < f[u]\)
• D. \(d[u] < d[v] < f[u] < f[v]\)

Hint:

DFS discovery/finish intervals are always either nested or disjoint, never partially overlapping; and a DAG produces no back edges.

Answer 1

The Correct Option is B, D

Step 1: Concept - the Parenthesis Theorem of DFS.
For any two vertices \(u,v\) explored during a DFS, their discovery/finish intervals \([d[u],f[u]]\) and \([d[v],f[v]]\) are either completely disjoint or one is nested entirely within the other. Interleaved-but-not-nested intervals can never occur. In addition, if \(v\) is discovered while \(u\) is still active (\(d[u] < d[v] < f[u]\)), then \(v\) must be a descendant of \(u\) in the DFS tree, which forces \(v\)'s whole interval to sit inside \(u\)'s interval, i.e. \(f[v] < f[u]\).

Step 2: Classify edges by interval pattern.
Tree/forward edge (u ancestor of v, v inside u's interval): \(d[u] < d[v] < f[v] < f[u]\) - option (A).
Back edge (v ancestor of u, u inside v's interval, edge points back to an ancestor): \(d[v] < d[u] < f[u] < f[v]\) - option (B).
Cross edge (v already fully explored via an unrelated branch before u starts): \(d[v] < f[v] < d[u] < f[u]\) - option (C).
Option (D), \(d[u] < d[v] < f[u] < f[v]\), describes v starting inside u's interval but finishing after u - an interleaved, non-nested pattern.

Step 3: Option (A) is possible.
This is the ordinary tree-edge or forward-edge pattern and occurs whenever u is an ancestor of v in the DFS forest, which is entirely normal in a DAG. So (A) CAN happen.

Step 4: Option (C) is possible.
Example: vertices 1, 2, 3 with only the edge 3 to 1, processed by the outer loop in order 1, 2, 3. DFS visits 1 first: \(d[1]=1, f[1]=2\). Then visits 2 (no edges): \(d[2]=3, f[2]=4\). Then visits 3, explores edge (3,1): 1 is already marked so nothing new happens, and 3 finishes: \(d[3]=5, f[3]=6\). Here \(d[1]=1 < f[1]=2 < d[3]=5 < f[3]=6\), matching option (C) exactly, with no cycle created. So (C) CAN happen.

Step 5: Option (B) can NEVER happen in a DAG.
Pattern (B) means \(u\)'s entire interval is nested inside \(v\)'s interval with v discovered first, so by the descendant lemma of Step 1, u is a descendant of v in the DFS tree. Since (u,v) is a real edge of G going from the descendant u back up to its ancestor v, this is by definition a back edge, and a back edge exists in a directed graph's DFS if and only if that graph contains a cycle. Because G is given to be a DAG (acyclic), no back edge can ever arise, so pattern (B) is impossible for any edge of G.

Step 6: Option (D) can NEVER happen, in any directed graph at all.
If \(d[u] < d[v] < f[u]\), v is discovered while u is still active, so by the descendant lemma v must be a descendant of u, and its entire interval must be nested inside u's, forcing \(f[v] < f[u]\). This directly contradicts the requirement \(f[u] < f[v]\) in option (D). So (D) violates the Parenthesis Theorem itself and can never occur, independent of whether G is a DAG.

Step 7: Conclusion.
(A) and (C) are achievable patterns (tree/forward and cross edges). (B) is impossible because G is acyclic (no back edges exist). (D) is impossible because it violates the fundamental nesting property of DFS intervals.

\[ \boxed{\text{Correct options: (B) and (D)}} \]