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\).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Aleliunas, R.; Karp, R. M.; Lipton, R. H.; Lovasz, L.; Rackoff, C., Random walks, universal traversal sequences, and complexity of maze problems, (Proc. 20th Annual Symp. on Foundations of Computer Science (1979)), 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, (Presented at: Internat. Symp. über Logik und Algorithmik zu Ehren von Professor Hort Specker. Presented at: Internat. Symp. über Logik und Algorithmik zu Ehren von Professor Hort Specker, Zürich, Switzerland (1980)) · 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; 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, (Proc. 15th Symp. on Theory of Computing. Proc. 15th Symp. on Theory of Computing, Boston, MA (1983)), 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, (Proc. 10th ACM Symp. on Theory of Computation (1978)), 114-118 · Zbl 1282.68104 |
| [10] | Goldschlager, L., A unified approach to models of synchronous parallel machines, (Proc. 10th Annual ACM Symp. on the Theory of Computing. Proc. 10th Annual ACM Symp. on the Theory of Computing, San Diego, CA (1978)), 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: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [17] | Ja’ja’, J., Graph connectivity problems on parallel computers, (Tech. Rept. GS-78-05 (1978), Dept. of Computer Science, Penn. State Univ: Dept. of Computer Science, Penn. State Univ PA) |
| [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, (Proc. 14th Annual ACM Symp. on Theory of Computing. Proc. 14th Annual ACM Symp. on Theory of Computing, San Francisco, CA (1982)), 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) · Zbl 0558.68038 |
| [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, (Ph.D. Thesis and Tech. Rept. 79-387 (1979), Dept. of Computer Science, Cornell University) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
