S-T Connectivity on Digraphs with a Known Stationary Distribution

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 (O. Reingold, Journal of the ACM, 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 o