UNDIRECTED S-T CONNECTIVITY IN POLYNOMIAL-TIME AND SUBLINEAR SPACE

The s-t connectivity problem for undirected graphs is to decide whethe r two designated vertices, s and t, are in the same connected componen t. This paper presents the first known deterministic algorithms solvin g undirected s-t connectivity using sublinear space and polynomial tim e. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. For n vertex, m edge graph s, 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 th e higher end of the space spectrum. For example, with space Theta(n lo g n), its time bound is O((m + n) log n), close to the optimal time fo r 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 la mbda the time remains polynomial.