Depth-first search is inherently sequential. (English) Zbl 0572.68051

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\).


68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Aleliunas, R.; Karp, R.M.; Lipton, R.H.; Lovasz, L.; Rackoff, C., Random walks, universal traversal sequences, and complexity of maze problems, (), 218-223
[2] Chin, F.; Lam, J.; Chen, I., Optimal parallel algorithms for the connected components problem, (1981), Foundations of Computer Science (FOCS)
[3] Cook, S.A., An observation on time-storage trade off, J. comput. system sci., 9, 3, 308-316, (1974) · Zbl 0306.68026
[4] Cook, S.A., Towards a complexity theory of synchronous parallel computation, () · Zbl 0484.68036
[5] Dobkin, D.; Lipton, R.J.; Reiss, S., Linear programming is log-space hard for P, Inform. process. lett., 9, 2, 96-97, (1979) · Zbl 0402.68042
[6] Dymond, P.W., Speed-up of multi-take Turing machines by synchronous parallel machines, Tech. Rept., Dept. of EE and Computer Science, Univ. of California, San Diego, CA
[7] Dymond, P.W.; Tompa, M., Speed-ups of deterministic machines by synchronous parallel machines, (), 336-346
[8] Even, S.; Tarjan, R.E., Network flow and testing graph connectivity, J. SIAM comput., 4, 4, 507-512, (1975) · Zbl 0328.90031
[9] Fortune, S.; Wyllie, J.C., Parallelism in random access machines, (), 114-118 · Zbl 1282.68104
[10] Goldschlager, L., A unified approach to models of synchronous parallel machines, (), 89-94 · Zbl 1282.68105
[11] Goldschlager, L.M.; Shaw, R.A.; Staples, J., The maximum flow problem is log-space complete for P, Theoret. comput. sci., 21, 105-111, (1982) · Zbl 0486.68035
[12] Hopcroft, J.E.; Karp, R.M., An \(n\^{}\{52\}\) algorithm for maximum matching in bipartite graphs, J. SIAM comput., 2, 225-231, (1973) · Zbl 0266.05114
[13] Hopcroft, J.E.; Tarjan, R.E., Efficient planarity testing, J. ACM, 21, 549-568, (1974) · Zbl 0307.68025
[14] Hopcroft, J.E.; Tarjan, R.E., Dividing a graph into triconnected components, SIAM J. comput., 2, 3, (1973) · Zbl 0281.05111
[15] Hopcroft, J.E.; Tarjan, R.E., Efficient algorithms for graph manipulation, Comm. ACM, 16, 6, 372-378, (1973) · Zbl 0281.05111
[16] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[17] Ja’ja’, J., Graph connectivity problems on parallel computers, ()
[18] Ja’ja’, J.; Simon, J., Parallel algorithms in graph theory: planarity testing, SIAM J. comput., 11, 2, 372-378, (1982)
[19] Jones, N.D.; Laaser, W.T., Complete problems for deterministic polynomial time, Theoret. comput. sci., 3, 1, 105-117, (1976) · Zbl 0352.68068
[20] Ladner, R.E., The circuit value problem is log-space complete for P, SIGACT news, 7, 1, 18-20, (1975)
[21] Miklail, A.J.; Kosaraju, S.R., Graph problems on a mesh-connected processor array, (), 345-353
[22] Reif, J.H., Symmetric complementation, J. ACM, 31, 2, 401-421, (1984) · Zbl 0632.68062
[23] Reif, J.H., On the power of probabilistic choice in synchronous parallel computations, SIAM J. comput., 13, 1, 46-55, (1984)
[24] Savage, C.; Ja’ja’, J., Fast, efficient parallel algorithms for some graph problems, SIAM J. comput., 10, 4, 682-691, (1981) · Zbl 0476.68036
[25] Tarjan, R.E., Depth-first search and linear graph algorithms, SIAM J. comput., 1, 2, 146-160, (1972) · Zbl 0251.05107
[26] Wyllie, J.C., The complexity of parallel computations, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.