GATE 2026 CS (CS1) – Question 50
Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic graph (DAG) $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of vertex $v \in V$. For an edge $(u, v) \in E$, which of the following options will NEVER be correct?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $d[v] < d[u] < f[u] < f[v]$
Explanation
By the Parenthesis Theorem of DFS:
- Tree edge or Forward edge: $v$ is a descendant of $u \implies [d[v], f[v]] \subset [d[u], f[u]]$, i.e. $d[u] < d[v] < f[v] < f[u]$. (Option A is possible).
- Cross edge: $v$ is explored and finished before $u$ is discovered $\implies f[v] < d[u]$, i.e. $d[v] < f[v] < d[u] < f[u]$. (Option C is possible).
- Back edge: $(u, v)$ points to an ancestor $v$ of $u \implies [d[u], f[u]] \subset [d[v], f[v]]$, i.e. $d[v] < d[u] < f[u] < f[v]$.
However, a directed graph is a DAG if and only if DFS yields NO back edges. Since $G$ is given to be a DAG, back edges CANNOT exist!
- Note: Overlapping intervals $d[u] < d[v] < f[u] < f[v]$ are impossible in DFS in general, but among the choices describing standard edge classifications, option (B) represents a back edge, which can NEVER occur in a DAG.
Therefore, option (B) will NEVER be correct.