This paper concerns the computational complexity of depth-first search. Suppose we are
given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first
visited before v in depth-first search order of G. We show that this problem, for undirected
and directed graphs, is complete in deterministic polynomial time with respect to
deterministic log-space reductions. This gives strong evidence that depth-first search
ordering can be done neither in deterministic space (log n) c nor in parallel time (log n) c, for …