Reducing space usage of st-connectivity with multiple passes? Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.

Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar 
Rajagopalan observed that $\Omega(n/k)$ space is necessary to determine whether there is a path between two given vertices in $G$, if $k$ passes are allowed over the data.  (See also the technical report version.)  However, they do not provide an algorithm to actually achieve this bound.  I assume that an optimal algorithm would actually take $O((n\, \log\, n)/k)$ space in a realistic computing model, since one has to distinguish the $n$ different vertices if one cannot index memory using constant size pointers.


  How can one decide graph connectivity with $k$ passes using $O((n\, \log\, n)/k)$ space?


If only one pass is allowed, the input data can be stored as a partition of the set of vertices, merging sets if an edge is seen between vertices in two different sets.  This clearly requires at most $O(n\, \log\, n)$ space.  My question is about $k &gt; 1$: how can one use more passes to reduce the required space?

(For avoidance of triviality, $k$ is a parameter that cannot be bounded a priori by a constant, and the space bounds are expressions involving functions of both $n$ and $k$.)



Update: even for $k=2$ it would be really useful to have a way to store only $n/2$ vertices.  Or is there actually a stronger lower bound $cn$ for some constant $c$, regardless of $k$?
It is a long standing open problem to find an algorithm for st-connectivity that runs in simultaneously sub-linear space and polynomial time, an easier task that what you are aiming at.  Such algorithms are known for the un-directed version, but even these require a large polynomial time (rather than O(km) time which would be implied by a k-pass algorithm).  See especially the reference to Tompa's paper on why the directed case seems hard.