S-T Connectivity on Digraphs with a Known Stationary Distribution

Kai-Min Chung, Omer Reingold, and Salil Vadhan


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, STOC `05).  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).


 [ back to Salil Vadhan's research]