S-T Connectivity on Digraphs with a Known Stationary Distribution
Kai-Min Chung, Omer Reingold, Salil Vadhan · Proceedings - IEEE Conference on Computational Complexity/Proceedings · 2007
We present a deterministic logspace algorithm for solving S-T CONNECTIVITY on directed graphs if (i) we are given a stationary distribution for random walk on the graph 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 [15]. 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).