Item

Abstract

Directed $s$-$t$ 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)$
and $S^{1/2}T = \Omega(m n^{1/2})$
for Cook and Rackoff's JAG model, where $n$ is the number of
vertices and $m$ the number of edges in the input graph, and
$S$ is the space and $T$ the time used by the JAG.
We also prove a time-space lower bound of
$S^{1/3}T = \Omega(m^{2/3}n^{2/3})$
on the more powerful
node-named JAG model of Poon.
These bounds approach the known upper bound
of $T = O(m)$
when $S = \Theta(n \log n)$.