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: Think of DFS as placing a left parenthesis at \(d[x]\) and a matching right parenthesis at \(f[x]\) for every vertex x. A legal, well-formed sequence of parentheses can only show two shapes for a pair of vertices: fully separate pairs \((\ )(\ )\), or one pair properly nested inside the other \((\ (\ )\ )\). No legal parenthesization ever produces a partially overlapping shape \((\ (\ )\).

Step 2: Option (D) states \(d[u] < d[v] < f[u] < f[v]\), which is literally the partially-overlapping shape \((_u\ (_v\ )_u\ )_v\). This shape can never be produced by any well-nested bracket process, so it is impossible for ANY pair of vertices in ANY DFS run, DAG or not. Rule this option out immediately on that basis.

Step 3: Option (B), \(d[v] < d[u] < f[u] < f[v]\), is a legal nesting shape \((_v\ (_u\ )_u\ )_v\), so it is not ruled out by the parenthesis structure alone; it says v's parenthesis pair fully contains u's, meaning v is an ancestor of u in the DFS forest. Since the edge in question runs from u to v, and v is an ancestor of u, this edge closes a path from v down to u and back up via the edge (u,v) - exactly a cycle \(v \to \dots \to u \to v\). A directed graph contains such a cycle exactly when its DFS produces this nesting pattern on a real edge (the standard back-edge test). The problem guarantees G is acyclic, so this pattern, though structurally legal in the abstract, can never be realised by an actual edge of this particular G.

Step 4: Options (A) \(d[u] < d[v] < f[v] < f[u]\) and (C) \(d[v] < f[v] < d[u] < f[u]\) are the two remaining legal shapes: (A) is u's pair containing v's pair (u ancestor of v - tree/forward edge), and (C) is two fully disjoint pairs with v's pair entirely finished before u's begins (cross edge). Both shapes are realised routinely inside an acyclic graph's DFS - a small worked trace (e.g. vertices 1,2,3 with the single edge 3 to 1, visited in order 1,2,3) produces \(d[1]=1,f[1]=2,d[3]=5,f[3]=6\), matching pattern (C) for edge (3,1). Any simple parent-child edge produces pattern (A). So both (A) and (C) are achievable.

Step 5: Only (B) and (D) can never be the pattern for a real edge of an acyclic G - (D) is forbidden by the bracket structure itself, and (B) is forbidden because it would certify a cycle that the DAG assumption rules out.

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