S-T connectivity on digraphs with a known stationary distribution
Abstract
We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices s and t have nonnegligible probability mass and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T Connectivity on undirected graphs [Reingold, 2008]. It identifies knowledge of the stationary distribution as the gap between the S-T Connectivity problems we know how to solve in logspace ( L ) and those that capture all of randomized logspace ( RL ).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 01, 2011
- Source ID
- 10.1145/1978782.1978785
Entities
People
- Kai-Min Chung
- Omer Reingold
- Salil Vadhan
Organizations
- Division of Computing and Communication Foundations
- Harvard University
- Microsoft
- Office of Naval Research