# S-T Connectivity on Digraphs with a
Known Stationary Distribution

Kai-Min Chung, Omer Reingold, and Salil Vadhan

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

### Versions

- In
*Proceedings of the 22nd
Annual IEEE Conference on Computational Complexity (CCC `07),* pages
96-108, 12-16 June 2007. [pdf][IEEE page]
*Electronic Colloquium on
Computational Complexity, *Technical Report TR07-30, March 2007. [ECCC
page]
- Minor revision, September
2007. [pdf]
- Final version to appear in
*ACM Transactions on Algorithms. *[pdf]

[ back to Salil
Vadhan's research]