Undirected ST-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 [9]. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, 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 [45] 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 labelling 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 conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 2: R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, pages 218--223. IEEE, 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: N. Alon and V. D. Milman. λsb 1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73--88, 1985.
• 6: N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271--284, 1994.
• 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: C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC), 3(039), 1996.
• 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: László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
• 11: 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]
• 12: A. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In 28th FOCS, pages 286--294, 1987.
• 13: J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, 11(4):331--362, 1991.
• 14: 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]
• 15: O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci., 22(3):407--420, June 1981.
• 16: 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
• 17: 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]
• 18: 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]
• 19: Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
• 20: M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th Structures in Complexity conference, pages 102--111, 1993.
• 21: 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]
• 22: Michal Koucky, Universal Traversal Sequences with Backtracking, Proceedings of the 16th Annual Conference on Computational Complexity, p.21, June 18-21, 2001
• 23: Michal Koucky , Eric Allender, On traversal sequences, exploration sequences and completeness of kolmogorov random strings, 2003
• 24: H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theor. Comput. Sci., 19:161--187, 1982.
• 25: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 26: 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
• 27: G. A. Margulis. Explicit constructions of expanders. Problemy Peredaci Informacii, 9(4):71--80, 1973.
• 28: G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51--60, 1988.
• 29: 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
• 30: 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]
• 31: 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]
• 32: N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449--461, 1992.
• 33: N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in o(log1.5n) space. In Proceedings of the 30th FOCS, pages 24--29. IEEE, 1989.
• 34: N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci., 1995.
• 35: 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]
• 36: M. S. Pinsker. On the complexity of a concentrator. In 7th Annual Teletraffic Conference, pages 318/1--318/4, 1973.
• 37: 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]
• 38: John H. Reif, Symmetric Complementation, Journal of the ACM (JACM), v.31 n.2, p.401-421, April 1984 [doi>10.1145/62.322436]
• 39: O. Reingold, L. Trevisan, and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem. ECCC Technical Report TR05-022, 2005.
• 40: 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
• 41: 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
• 42: 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]
• 43: J. Savitch. Relationship between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177--192, 1970.
• 44: M. R. Tanner. Explicit concentrators from generalized n-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287--293, 1984.
• 45: 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]
• 46: 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
• 47: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms, Theory