Depth-first search is inherently sequential (Q1062456)

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 any constant \(c>0\).