Undirected S-T connectivity in polynomial time and sublinear space

The s-t connectivity problem for undirected graphs is to decide whether two designated vertices, s and t, are in the same connected component. This paper presents the first known deterministic algorithms solving undirected s-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. For n vertex, m edge graphs, the simplest of our algorithms uses space O(s), n(1/2)log(2)n less than or equal to s less than or equal to nlog(2)n, and time O(((m + n)n(2)log(2)n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space Theta(n log n), its time bound is O((m + n) log n), close to the optimal time for the problem. Another generalization uses less space, but more time: space O(lambda n(1/lambda) log n), for 2 less than or equal to lambda less than or equal to log(2) n, and time n(O(lambda)). For constant lambda the time remains polynomial.