TL’DR : in a DAG, a mutually unreachable pair (s,t) can exist if and only if there exists at least one topological level with at least two nodes.

An interesting question came during the Course COMP-550(Algo Analysis) at UNC-CH. Analysing the solution provided by instructor and then playing with ChatGPT along with my own intution helped be develop some key takeaways about DAG.

Unreachable Pair in a D.A.G

<aside> 💡

Problem: The input is a DAG G. Our goal is to return a pair of vertices (s, t) such that s cannot reach t and t cannot reach s (or nothing, if no such pair exists). Describe an O(m+n)-time algorithm for this problem, explain why it’s correct, and analyze its running time.

</aside>

Some key observations on given problem :

• Acyclic ⇒ for any (u, v) if u⤳v path exists then u⬿v path cannot exist.
• O(m+n) running time limitation ⇒ hints nodes cannot be probed worse than DFS/BFS traversal.
• Recall : Topological Ordering is nothing but “return V in order of decreasing post value.”
• If we traverse the nodes in topological order and u comes before v, then non-existence of u→v path is sufficient to prove (u,v) are unreachable pairs. That is, there is no need to prove non-existence of v→u path because graph is acyclic.
  • for any (u, v) if u topologically precedes v then, if u⤳v path doesn’t exists then u & v are unreachable pairs.

Solution provided by our instructor :

Solution. Let T be a topological ordering of V . If there exists i such that (T[i], T[i + 1]) ∉ E, then

return (T[i], T[i + 1]); otherwise, return nothing:

1 ALG(G):
2    T = topological ordering of V
3    for i = 1, ..., n-1:
4        if (T[i], T[i+1]) is not in E:
5            return (T[i], T[i+1])

Suppose the algorithm returns (T[i], T[i + 1]). Then T[i] cannot reach T[i + 1] because each edge leaving T[i] points to some vertex T[j] where j > i + 1, and no edges point backward. Similarly, T[i + 1] cannot reach T[i]. Conversely, if (T[i], T[i + 1]) ∈ E for all i ∈ {1, . . . , n - 1}, then for any pair of vertices (T[i], T[j]) where i < j, T[i] can reach T[j] by following these edges.

Ordering V takes O(m + n) time, and we can find any missing edge (T[i], T[i + 1]) in O(m + n) time. Note that for each vertex u, we scan the list G[u] at most once, so the total running time of scanning the n - 1 lists is O(m + n) (similar to BFS).

Many questions arose after reading line #4 of pseudocode if (T[i], T[i+1]) is not in E: