TIME-SPACE LOWER BOUNDS FOR DIRECTED ST-CONNECTIVITY ON GRAPH AUTOMATA MODELS

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(n2 log n/log(n log n/S) and S-1/2 T = Omega(m(n log n)(1/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 o f vertices and m the number of edges in the input graph, S is the spac e, and T the time used by the JAG. These lower bounds are simple and e legant, they approach the known upper bound of T = O(m) when S approac hes Theta(n log n), and they are the first time-space tradeoffs for JA Gs with an unrestricted number of jumping pebbles.