Randomized Time Space Tradeoffs for Directed Graph Connectivity

Abstract. We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and performs short random walks of length n 1 k using a probabilistic counter. We use this to get a family of algorithms that ranges between log 2 n and log n in space and 2 log2 n and n n in running time. Our approach allows us to look at Savitch’s algorithm and the random walk algorithm as two extremes of the same basic divide and conquer strategy.