# S-T connectivity on digraphs with a known stationary distribution

### Citation:

Chung, Kai-Min, Omer Reingold, and Salil Vadhan. “S-T connectivity on digraphs with a known stationary distribution.” In ACM Transactions on Algorithms. Vol. 7. 3rd ed. ACM, 2011.
 ECCC2007.pdf 263 KB ACM2011.pdf 223 KB

### Abstract:

Version history: Preliminary versions in CCC '07 and on ECCC (TR07-030).

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).

Publisher's Version

Last updated on 07/15/2020