Undirected connectivity in log-space

TLDR

Previous work bounded undirected st‑connectivity space complexity at log 4/3, and Trifonov later achieved an O(log n log log n) deterministic log‑space algorithm. We present a deterministic log‑space algorithm that solves undirected st‑connectivity. The algorithm deterministically computes st‑connectivity within logarithmic space. This algorithm establishes SL = L and yields log‑space constructible universal traversal and exploration sequences for connected graphs.

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.