Center for Research in Computing Technology, Aiken Computation Laboratory, Division of Applied Science, Harvard University, Cambridge, MA 02138, U.S.A.
Abstract:
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.