[ACM Press the thirty-seventh annual ACM symposium - Baltimore, MD, USA (2005.05.22-2005.05.24)] Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05 - Undirected ST-connectivity in log-space

✍ Scribed by Reingold, Omer

• Book ID: 121205027
• Publisher: ACM Press
• Year: 2005
• Tongue: English
• Weight: 203 KB
• Category: Article
• ISBN-13: 9781581139600
• DOI: 10.1145/1060590.1060647

✦ Synopsis

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, logspace 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 logspace a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give universal-traversal sequences, constructible in logarithmic space, for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.