Depth-first search is inherently sequential

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. © 1985.

Duke Scholars

Author John H. Reif Computer Science