Undirected connectivity in log-space

ABSTRACT

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log^4/3(⋅) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity.

Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.

REFERENCES

• 1: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 2: Romas Aleliunas , Richard M. Karp , Richard J. Lipton , Laszlo Lovasz , Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), p.218-223, October 29-31, 1979
• 3: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 4: N. Alon , Z. Galil , V. D. Milman, Better expanders and superconcentrators, Journal of Algorithms, v.8 n.5, p.337-347, Sept. 1987 [doi>10.1016/0196-6774(87)90014-9]
• 5: Alon, N., and Milman, V. D. 1985. λ₁, isoperimetric inequalities for graphs, and superconcentrators. J. Combinat. Theory Ser. B 38, 1, 73--88.
• 6: Alon, N., and Roichman, Y. 1994. Random Cayley graphs and expanders. Rand. Struct. Algorithms 5, 2, 271--284.
• 7: Noga Alon , Benny Sudakov, Bipartite Subgraphs and the Smallest Eigenvalue, Combinatorics, Probability and Computing, v.9 n.1, p.1-12, January 2000 [doi>10.1017/S0963548399004071]
• 8: Alvarez, C., and Greenlaw, R. 1996. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC) 3, 039.
• 9: Roy Armoni , Amnon Ta-Shma , Avi Widgerson , Shiyu Zhou, An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs, Journal of the ACM (JACM), v.47 n.2, p.294-311, March 2000 [doi>10.1145/333979.333984]
• 10: 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]
• 11: Y. Ben-Asher , K.-J. Lange , D. Peleg , A. Schuster, The complexity of reconfiguring network models, Information and Computation, v.121 n.1, p.41-58, Aug. 15, 1995 [doi>10.1006/inco.1995.1122]
• 12: A. Borodin , S. A. Cook , P. W. Dymond , W. L. Ruzzo , M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, v.18 n.3, p.559-578, June 1989 [doi>10.1137/0218038]
• 13: Andrei Broder , Eli Shamir, On the second eigenvalue of random regular graphs, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), p.286-294, October 12-14, 1987 [doi>10.1109/SFCS.1987.45]
• 14: Chung, K.-M., Reingold, O., and Vadhan, S. 2007. S-T connectivity on digraphs with known stationary distribution. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC), In IEEE Computer Society Press, Los Alamitos, CA, 236--249. (Full version posted as ECCC TR07-030).
• 15: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
• 16: Friedman, J. 1991. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11, 4, 331--362.
• 17: J. Friedman , J. Kahn , E. Szemerédi, On the second eigenvalue of random regular graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.587-598, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73063]
• 18: Gabber, O., and Galil, Z. 1981. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 3 (June), 407--420.
• 19: Goldreich, O. 2005. Bravely, moderately: A common theme in four recent results. Electronic Colloquium on Computational Complexity (ECCC) 098. (Also appeared as part of SIGACT news complexity theory column 51.)
• 20: Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, New York, NY, 2008
• 21: Oded Goldreich , Avi Wigderson, Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.209-223, September 13-15, 2002
• 22: Shlomo Hoory , Avi Wigderson, Universal traversal sequences for expander graphs, Information Processing Letters, v.46 n.2, p.67-69, May 17, 1993 [doi>10.1016/0020-0190(93)90199-J]
• 23: Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195190]
• 24: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 25: Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
• 26: Karchmer, M., and Wigderson, A. 1993. On span programs. In Proceedings of the 8th Structures in Complexity conference. 102--111.
• 27: Adam R. Klivans , Dieter van Melkebeek, Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses, SIAM Journal on Computing, v.31 n.5, p.1501-1526, 2002 [doi>10.1137/S0097539700389652]
• 28: Michal Koucky, Universal Traversal Sequences with Backtracking, Proceedings of the 16th Annual Conference on Computational Complexity, p.21, June 18-21, 2001
• 29: Michal Koucky , Eric Allender, On traversal sequences, exploration sequences and completeness of kolmogorov random strings, Rutgers University, New Brunswick, NJ, 2003
• 30: Lewis, H. R., and Papadimitriou, C. H. 1982. Symmetric space-bounded computation. Theoret. Comput. Sci. 19, 161--187.
• 31: Lubotzky, A., Phillips, R., and Sarnak, P. 1988. Ramanujan graphs. Combinatorica 8, 3, 261--277.
• 32: N. Madras , D. Randall, Factoring graphs to bound mixing rates, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.194, October 14-16, 1996
• 33: Margulis, G. A. 1973. Explicit constructions of expanders. Problemy Peredachi Informatsii 9, 4, 71--80.
• 34: Margulis, G. A. 1988. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24, 1, 51--60.
• 35: R. A. Martin , D. Randall, Sampling adsorbing staircase walks using a new Markov chain decomposition method, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.492, November 12-14, 2000
• 36: Moshe Morgenstern, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory Series B, v.62 n.1, p.44-62, Sept. 1994 [doi>10.1006/jctb.1994.1054]
• 37: Nisan, N. 1992a. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449--461.
• 38: Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
• 39: N. Nisan , E. Szemeredi , A. Wigderson, Undirected connectivity in O(log/sup 1.5/n) space, Proceedings of the Proceedings., 33rd Annual Symposium on Foundations of Computer Science, p.24-29, October 24-27, 1992 [doi>10.1109/SFCS.1992.267822]
• 40: Nisan, N., and Ta-Shma, A. 1995. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci.
• 41: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 42: Pinsker, M. S. 1973. On the complexity of a concentrator. In Proceedings of the 7th Annual Teletraffic Conference. Stockholm, 318/1--318/4.
• 43: Ran Raz , Omer Reingold, On recycling the randomness of states in space bounded computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.159-168, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301294]
• 44: John H. Reif, Symmetric Complementation, Journal of the ACM (JACM), v.31 n.2, p.401-421, April 1984 [doi>10.1145/62.322436]
• 45: Omer Reingold , Luca Trevisan , Salil Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132583]
• 46: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 47: Reingold, O., Vadhan, S., and Wigderson, A. 2002. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math. 155, 1 (January). (Extended abstract in Proceedings of FOCS '00).
• 48: Rozenman, E., and Vadhan, S. 2005. Derandomized squaring of graphs. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM). Lecture Notes in Computer Science, vol. 3624. Springer-Verlag, New York, 436--447.
• 49: Michael Saks, Randomization and Derandomization in Space-Bounded Computation, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.128, May 24-27, 1996
• 50: Michael Saks , Shiyu Zhou, BPH SPACE(S) ⊆ DSPACE(S3/2), Journal of Computer and System Sciences, v.58 n.2, p.376-403, April 1999 [doi>10.1006/jcss.1998.1616]
• 51: Savitch, J. 1970. Relationship between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4, 2, 177--192.
• 52: Tanner, M. R. 1984. Explicit concentrators from generalized n-gons. SIAM J. Algeb. Disc. Meth. 5, 3, 287--293.
• 53: Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060684]
• 54: Avi Wigderson, The Complexity of Graph Connectivity, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.112-132, August 24-28, 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
Derandomization, bounded space algorithms, pseudorandom generator