A space lower bound for st-connectivity on node-named JAGs
Given a directed graph G and two of its nodes s and t, the directed st-connectivity problem (STCON) is to decide whether there is a directed path From s to t in G, Establishing a lower bound For STCON on a general computation model such as Turing machine or branching program has been a big challenge in complexity theory. As an intermediate step, Cook and Rackoff (SIAM J. Comput, 9(3) (1980) 636-652) introduce a structured model called JAG (jumping automaton for graphs) and prove a space lower bound of Omega(log(2)n/log log n) on this model. Berman and Simon (Proc, 24th Annual Symp. on Foundations of Computer science, IEEE press, New York, Tucson, AZ, November 1983) show a similar lower bound for a probabilistic JAG. We take a step further by introducing a stronger model called NN-JAG (Node-named JAG) and obtain the same space lower bound of Omega(log(2)n/log log n). On a probabilistic NNJAG, we show that S = Omega(log(2)n/(log log n + log log T)) where S is the space and T is the expected time used, respectively, This gives the best expected time lower bound on this model when the space S is O(log(2)n/log log n). (C) 2000 Elsevier Science B.V. All rights reserved.
space lower bound graph complexity connectivity