Faster Walks in Graphs: A Õ(n2) Time-Space Trade-off for Undirected s-t Connectivity

DOI10.1137/1.9781611973105.133zbMath1423.68585arXiv1204.1136OpenAlexW2970794762MaRDI QIDQ5741843

Adrian Kosowski

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the $S$-$T$-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 $ScdotT=ildeO(n^2)$ in graphs with $n$ nodes and $m$ edges (where the $ildeO$-notation disregards poly-logarithmic terms). This improves the previously best trade-off of $ildeO(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 $ildeO(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 $ildeO(n^2)$ on cover time.

Full work available at URL: https://arxiv.org/abs/1204.1136

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Randomized algorithms (68W20) Random walks on graphs (05C81)

This page was built for publication: Faster Walks in Graphs: A Õ(n²) Time-Space Trade-off for Undirected s-t Connectivity