2012/04/05 by Adrian Kosowski, Kosowski, Adrian
Computer Science · Materials Science · #Carbon and Quantum Dots Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1204.1136
openalex publication_date 2012/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 S⋅ T = O(n2) in graphs with n nodes and m edges (where the O-notation disregards poly-logarithmic terms). This improves the previously best trade-off of O(n m), 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 O(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 O(n2) on cover time.