Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models
Greg Barnes, Jeff A. Edmonds · SIAM Journal on Computing · 1998
Directed st-connectivity is the problem of detecting whether there is a path from a distinguished vertex s to a distinguished vertex t in a directed graph. We prove time--space lower bounds of $ST = \Omega({n^{2} \log n \over \log (n \log n/S)})$ and $S^{1 \over 2}T = \Omega(m (n \log n)^{1 \over 2})$ for directed st-connectivity on Cook and Rackoff's jumping automaton for graphs (JAG) model [SIAM J. Comput., 9(1980), pp. 636--652], where n is the number of vertices and m the number of edges in the input graph, S is the space, and T the time used by the JAG. These lower bounds are simple and elegant, they approach the known upper bound of T = O(m) when S approaches $\Theta(n \log n)$, and they are the first time--space tradeoffs for JAGs with an unrestricted number of jumping pebbles.