Theoretical Computer Science

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 > 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$?

Solution

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.

• +0This paper gives "an algorithm for st-connectivity that runs in simultaneously $\hspace{1.71 in}$ sub-linear space and polynomial time". — Feb 04, 2017 at 04:57