Random Walks on Some Basic Classes of Digraphs

摘要

Reingold has shown that L=SL, that s-t connectivity in a poly-mixing digraph is complete for promise-RL, and that s-t connectivity for a poly-mixing out-regular digraph with known stationary distribution is in L. However, little work has been done on identifying structural properties of digraphs that effect cover times. We examine the complexity of random walks on a basic parameterized family of unbalanced digraphs called Strong Chains (which model weakly symmetric computation), and a special family of Strong Chains called Harps. We show that the worst case hitting times of Strong Chain families vary smoothly with the number of asymmetric vertices and identify the necessary condition for non-polynomial cover time. This analysis also yields bounds on the cover times of general digraphs. Our goal is to use these structural properties to develop space efficient digraph modification for randomized search and to develop derandomized search strategies for digraph families.