Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space (Q677988)

The \(s\)-\(t\) connectivity problem for undirected graphs is to decide whether two designated vertices, \(s\) and \(t\), are in the same connected component. The authors present three new deterministic algorithms solving undirected \(s\)-\(t\) connectivity using sublinear space and polynomial time. The 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 their algorithms uses space \(O(s)\), \(n^{1/2}\log_2 n\leq s\leq n\log_2n\), and time \(O(((m+n)n^2 \log^2n)/s)\). They 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\leq\lambda\leq \log_2n\), and time \(N^{O(\lambda)}\). For constant \(\lambda\) the time remains polynomial.