Question

Consider the following pseudocode for depth-first search (DFS) algorithm which
takes a directed graph 𝐺(𝑉, 𝐸) as input, where 𝑑[𝑣] and 𝑓[𝑣] are the discovery time
and finishing time, respectively, of the vertex 𝑣 ∈𝑉.
𝐷𝐹𝑆(𝐺):
𝑢𝑛𝑚𝑎𝑟𝑘 𝑎𝑙𝑙 𝑣∈𝑉
𝑡 ←0
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑣∈𝑉
𝑖𝑓 𝑣 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑
𝑡←𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡)
𝑒𝑛𝑑 𝑖𝑓
𝑒𝑛𝑑 𝑓𝑜𝑟
𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡):
𝑚𝑎𝑟𝑘 𝑣
𝑡 ←𝑡+ 1
𝑑[𝑣] ←𝑡
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ (𝑣, 𝑤) ∈𝐸
𝑖𝑓 𝑤 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑
𝑡←𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑤, 𝑡)
𝑒𝑛𝑑 𝑖𝑓
𝑒𝑛𝑑 𝑓𝑜𝑟
𝑡 ←𝑡 + 1
𝑓[𝑣] ←𝑡
𝑟𝑒𝑡𝑢𝑟𝑛 𝑡
Suppose that the input directed graph 𝐺(𝑉, 𝐸) is a directed acyclic graph (DAG).
For an edge (𝑢, 𝑣) ∈𝐸, which of the following options will NEVER be correct?

• A. 𝑑[𝑢] < 𝑑[𝑣] < 𝑓[𝑣] < 𝑓[𝑢]
• B. 𝑑[𝑣] < 𝑑[𝑢] < 𝑓[𝑢] < 𝑓[𝑣]
• C. 𝑑[𝑣] < 𝑓[𝑣] < 𝑑[𝑢] < 𝑓[𝑢]
• D. 𝑑[𝑢] < 𝑑[𝑣] < 𝑓[𝑢] < 𝑓[𝑣]

Hint:

Recall the Parenthesis Theorem: DFS intervals \([d[x], f[x]]\) for any two vertices are always either nested or disjoint, never partially overlapping. Check which option shows partial overlap (structurally impossible always) and which option matches the back-edge pattern (impossible only because the graph is a DAG, i.e. acyclic).

Answer 1

The Correct Option is B, D

This question tests the Parenthesis Theorem of DFS timestamps applied to a directed acyclic graph (DAG). For any edge \((u, v) \in E\) discovered during a DFS run, the discovery time \(d[\cdot]\) and finishing time \(f[\cdot]\) of \(u\) and \(v\) must satisfy one of a fixed set of relationships depending on the type of edge (tree/forward, back, or cross).

Step 1: Recall the Parenthesis Theorem.

In any DFS, for two vertices \(u\) and \(v\), the intervals \([d[u], f[u]]\) and \([d[v], f[v]]\) are either completely disjoint or one is completely nested inside the other. They can never partially overlap.

Step 2: Classify edge \((u, v)\) by DFS timestamp pattern.

Case 1 (Tree/Forward edge): \(u\) is an ancestor of \(v\) in the DFS forest, so \(v\)'s interval is nested inside \(u\)'s interval: \[d[u] < d[v] < f[v] < f[u]\] This is option A, and it is perfectly valid, so it is not the answer.

Case 2 (Cross edge): \(v\) is explored and completely finished before \(u\) is even discovered, so the intervals are disjoint with \(v\)'s interval entirely before \(u\)'s: \[d[v] < f[v] < d[u] < f[u]\] This is option C, and cross edges are valid in a DAG, so it is not the answer.

Case 3 (Back edge): \(v\) is an ancestor of \(u\), meaning \(v\)'s interval nests \(u\)'s interval: \[d[v] < d[u] < f[u] < f[v]\] This is exactly option B. A back edge implies a cycle in the graph (since \(v\) is an ancestor of \(u\) but there is also an edge \(u \to v\)). Since \(G\) is given to be a DAG, back edges cannot exist. Hence option B can never occur.

Step 3: Check option D.

Option D states \[d[u] < d[v] < f[u] < f[v]\] Here \(u\)'s interval starts before \(v\)'s, but \(u\) finishes before \(v\) finishes while \(v\) started after \(u\). This means the two intervals partially overlap: \(d[v]\) falls inside \(u\)'s interval, but \(f[v]\) falls outside it. This directly violates the Parenthesis Theorem, which forbids partial overlap between any two DFS intervals, regardless of whether an edge connects the vertices or whether the graph is a DAG. So option D is structurally impossible in any DFS run.

Step 4: Conclusion.

Option A (tree/forward edge pattern) and option C (cross edge pattern) are both valid and can occur. Option B (back edge pattern) cannot occur only because the graph is acyclic. Option D (overlapping intervals) can never occur in any DFS on any graph, because it violates the fundamental nesting property of DFS timestamps.

Hence the options that will NEVER be correct are B and D.

Final Answer:

\[\boxed{\text{Options B and D}}\]