Faster Walks in Graphs: A Õ(n2) Time-Space Trade-off for Undirected s-t Connectivity
Adrian Kosowski · 2013
In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the -connectivity problem in undirected graphs (USTCON). As our main result, we propose a family of randomized algorithms for USTCON which achieves a time-space product of S · T = Õ(n) in graphs with n nodes and m edges (where the Õ-notation disregards poly-logarithmic terms). This improves the previously best trade-off of Õ(nm), due to Feige (1995). Our algorithm consists in deploying several short Metropolis-type walks, starting from landmark nodes distributed using the scheme of Broder et al. (1994) on a modified input graph. In particular, we obtain an algorithm running in time Õ(n + m) which is, in general, more space-efficient than both BFS and DFS. We close the paper by showing how to fine-tune the Metropolis-type walk so as to match the performance parameters (e.g., average hitting time) of the unbiased random walk for any graph, while preserving a worst-case bound of Õ(n2) on cover time.