An O(log n log log n) space algorithm for undirected st-connectivity

ABSTRACT

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Koucký [13]. Our result improves the O(log^4/3 n) bound of Armoni et al.\ [2] and is a big step towards the optimal O(log n). Independently of our result and using a different set of techniques, the optimal bound was achieved by Reingold [18].

REFERENCES

• 1: R. Aleliunas, R. Karp, R. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th IEEE Symposium on Foundations of Computer Science, pages 218--223, 1979.
• 2: Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258593]
• 3: B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for ultracomputer and PRAM. In International Conference on Parallel Processing, pages 175--179, 1983.
• 4: Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
• 5: Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001 [doi>10.1145/375827.375847]
• 6: Ka Wong Chong , Tak Wah Lam, Finding connected components in O(log n log log n) time on the EREW PRAM, Journal of Algorithms, v.18 n.3, p.378-402, May 1995
• 7: R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree, and graph problems. In 27th IEEE Symposium on Foundations of Computer Science, pages 478--491, 1986.
• 8: H. Gazit. An optimal randomized parallel algorithm for finding connected components in a graph. In 27th IEEE Symposium on Foundations of Computer Science, pages 492--501, 1986.
• 9: Shay Halperin , Uri Zwick, Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.438-447, January 28-30, 1996, Atlanta, Georgia, United States
• 10: D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
• 11: Donald B. Johnson , Panagiotis Metaxas, Connected components in O(lg3/2|V|) parallel time for the CREW PRAM (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.688-697, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185437]
• 12: David R. Karger , Noam Nisan , Michal Parnas, Fast connected components algorithms for the EREW PRAM, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.373-381, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141920]
• 13: Michal Koucky, Universal Traversal Sequences with Backtracking, Proceedings of the 16th Annual Conference on Computational Complexity, p.21, June 18-21, 2001
• 14: H. Lewis and C. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19:161--187, 1982.
• 15: N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
• 16: N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(\log1.5 n) space. In 33rd IEEE Symposium on Foundations of Computer Science, pages 24--29, 1992.
• 17: Seth Pettie , Vijaya Ramachandran, A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest, SIAM Journal on Computing, v.31 n.6, p.1879-1895, 2002 [doi>10.1137/S0097539700371065]
• 18: Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060647]
• 19: C. Savage and J. JáJá. Fast, efficient parallel algorithms for some graph problems. SIAM Journal on Computing, 10(4):682--691, 1981.
• 20: W. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177--192, 1970.
• 21: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• 22: R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--160, 1972.
• 23: R. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862--874, 1985.
• 24: V. Trifonov. An O(log n log log n) space algorithm for undirected st-connectivity. Technical Report TR04-114, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
space complexity, space-bounded computation, space-efficient simulation of parallel algorithms, undirected st-connectivity