The Parenthesis Theorem for DFS Intervals

Discovery and Finish Times

Depth-first search (DFS) does more than record which vertices can be reached. In a recursive search, each vertex has a discovery event, when the search first visits it, and a finish event, when the search has examined all its outgoing edges and returns from its recursive call. The order of these events records the structure of the search: a vertex's recursive call remains active throughout the calls made below it. The Parenthesis Theorem makes this structure visible in the timestamps.

Throughout, graphs are finite and simple. For DFS examples, the graph is directed, and the outgoing neighbors of each vertex are examined in a specified order. The starting vertices (roots) are also considered in a specified order. These orders determine the particular DFS forest and timestamps.

With \(n\) vertices, each vertex is discovered once and finished once, so the event times are the distinct integers \(1,2,\ldots,2n\). In particular, \(d(v)<f(v)\) for every vertex. The convention of using closed intervals is harmless: all discovery and finish times are distinct, so two intervals belonging to different vertices never share an endpoint.

The Parenthesis Theorem

Proof. Because the event times are distinct, either \(d(u)<d(v)\) or \(d(v)<d(u)\). First suppose \(d(u)<d(v)\). At the moment \(v\) is discovered, one of two things must be true: the recursive call for \(u\) has already finished, or it is still active. If it has finished, then \(f(u)<d(v)\), so the intervals are disjoint. If it is still active, the call for \(v\) occurs during the call for \(u\). The call for \(v\) must finish before the search can finish the still-active call for \(u\). Therefore \(d(u)<d(v)<f(v)<f(u)\). The same argument with \(u\) and \(v\) interchanged applies when \(d(v)<d(u)\). The cases are mutually exclusive, which proves the result. \(\square\)

The proof uses the defining order of recursive DFS calls: a call cannot finish while a call made within it is still active. This is why the theorem applies to the discovery and finish times of a recursive DFS, rather than to arbitrary pairs of numbers attached to vertices.

Intervals Identify Ancestors

In a rooted DFS tree, a vertex \(u\) is an ancestor of \(v\) if \(u\) lies on the unique tree path from the root to \(v\). We count a vertex as its own ancestor. A vertex \(v\) is a descendant of \(u\) under the corresponding convention. For two distinct vertices, ancestry is exactly the strict containment relation between their intervals.

Proof. Suppose first that \(u\) is an ancestor of \(v\). The recursive call for \(v\) is made during the call for \(u\), and it must finish before the call for \(u\) finishes. Also, \(u\) is discovered before \(v\). These facts give \(d(u)<d(v)<f(v)<f(u)\).

Conversely, suppose \(d(u)<d(v)<f(v)<f(u)\). When \(v\) is discovered, the call for \(u\) has started but has not finished, since \(d(u)<d(v)<f(u)\). In recursive DFS, the active calls at any moment form the current recursion stack; each active call other than the last called vertex is an ancestor of that vertex in the DFS tree. Therefore \(u\) is on the active call stack when \(v\) is discovered, and \(u\) is an ancestor of \(v\). This proves both directions. \(\square\)

For a vertex compared with itself, the ancestor relation holds by convention and its interval equals itself; the strict inequalities in the theorem are therefore intended for distinct vertices. For distinct vertices, the Parenthesis Theorem says that if their intervals are not disjoint, one must be an ancestor of the other. Disjoint intervals mean that neither is an ancestor of the other.

Common Pitfall: Overlapping Is Not Enough

A common error is to infer ancestry merely because two intervals overlap. The Parenthesis Theorem requires that overlapping intervals be nested; partial overlap is impossible for a valid recursive DFS trace.

For a concrete incorrect calculation, consider a DFS call on the path \(s\to a\to b\). The assignment \(d(s)=1\), \(d(a)=2\), \(d(b)=3\), \(f(a)=4\), \(f(b)=6\), \(f(s)=8\) would give intervals \([2,4]\) for \(a\) and \([3,6]\) for \(b\). These overlap, but neither contains the other: \(2<3<4<6\). The assignment is wrong because it finishes \(a\) at time \(4\) while the recursive call for its descendant \(b\) is still active. A correct event order is \(d(s)=1,d(a)=2,d(b)=3,f(b)=4,f(a)=5,f(s)=6\), giving intervals \([1,6]\), \([2,5]\), and \([3,4]\). Now each descendant interval is strictly contained in the interval of its ancestors.

The theorem is useful whenever a DFS forest has been computed and one needs to answer ancestry questions from timestamps. For distinct vertices, compare the endpoints: \(d(u)<d(v)<f(v)<f(u)\) certifies that \(u\) is an ancestor of \(v\); \(f(u)<d(v)\) or \(f(v)<d(u)\) certifies that neither is an ancestor of the other. The interval test is valid only for discovery and finish times produced by a consistent DFS execution.