<p>This is not an answer, but I just wanted to point out that if you can solve this problem for $k = \Theta(n)$, then you solve st-connectivity in $O(\log n)$ space and $O(nm)$ time (which in the offline case you can do with probability > 1/2 by doing a random walk; but it seems a bit harder when the edges come from a stream). Very interesting question, IMO.</p>

CC BY-SA 3.0
2011-09-26T23:51:37.597Z
2011-09-26T23:51:37.597Z
zotachidil
<p>Yossi Shiloach, Uzi Vishkin. An O(log n) Parallel Connectivity Algorithm. J. Algorithms, 1982: 57~67   -- One of my favorite papers. It would be interesting if you could do it in O((nlogn/k)/p) space with p processors in $k$ rounds where each round each processor is only allowed to read in O(n/p) of the edges.</p>

CC BY-SA 3.0
2011-09-30T14:58:32.240Z
Thanks for the pointer, this is an interesting paper.  The processors have common access to a data structure that is at least as large as the graph, so this doesn't help to reduce space usage.  It would be indeed be interesting if there were a way to reduce space usage by exploiting the number of rounds as well as the number of processors.
András Salamon
CC BY-SA 3.0
2011-09-29T21:16:23.933Z
2011-09-29T21:16:23.933Z
Chad Brewbaker
<p>Yet another non-answer: there are some papers on mapreduce-style algorithms operating on large graphs. The goal is to achieve per-machine space o(m) for dense graphs, but typically need O(n) space per machine.</p>

<p>theory.stanford.edu/~sergei/papers/soda10-mrc.pdf
<a href="http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf" rel="nofollow">http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf</a></p>

CC BY-SA 3.0
2011-11-09T20:43:04.283Z
2011-11-09T20:43:04.283Z
Martin Pál
<p>Also not an answer, but you can decide st-connectivity in $O(n\log n/ k)$ non-deterministic space with $k$ passes. Just guess the first $n/k$ nodes of an $st$ path and check that they are connected in the first round, then continue from the last of these $n/k$ vertices and check the next $n/k$ from the $st$ path and so on.</p>

CC BY-SA 3.0
2011-11-05T07:21:31.797Z
2011-11-05T07:21:31.797Z
domotorp
<p>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 <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9770" rel="nofollow">un-directed version</a>, 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.</p>

CC BY-SA 3.0
2011-11-07T15:36:53.577Z
M. Tompa, _Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations_, SIAM J. Comput. 11(1), 130–137.  http://dx.doi.org/10.1137/0211010
András Salamon
CC BY-SA 3.0
2011-11-05T20:10:33.797Z
2011-11-05T20:10:33.797Z
Noam
<p>Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=327766.327782">Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar 
Rajagopalan</a> 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 <a href="http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1998-011.html">technical report version</a>.)  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.</p>

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

<p>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?</p>

<p>(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$.)</p>

<hr>

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

CC BY-SA 3.0
2011-11-04T21:27:08.630Z
How regardless of $k$? If it can be very big, then st-connectivity can be solved in $O(\log^2 n)$ space, so there is a chance for an algorithm, but as shown by azotlichid, probably not in $O(n\log n /k)$.
domotorp
CC BY-SA 3.0
2013-04-17T17:03:23.690Z
Note that Guha and McGregor's pass elimination for randomized algorithms works in the opposite direction, using more space to allow fewer passes (though the additional space is large if the desired error is small).  This question asks whether by using more passes, one can reduce the space usage.
András Salamon
<reference-request><graph-algorithms><ds.data-structures><lower-bounds><data-streams>
Reducing space usage of st-connectivity with multiple passes?
András Salamon
# Reducing space usage of st-connectivity with multiple passes?

(Asked by: username_0 on 2011-09-26)

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](http://dl.acm.org/citation.cfm?id=327766.327782) 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](http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1998-011.html).) 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$?

**Tags:** reference-request, graph-algorithms, ds.data-structures, lower-bounds, data-streams

> **Comments:**
> **username_1**: How regardless of $k$? If it can be very big, then st-connectivity can be solved in $O(\log^2 n)$ space, so there is a chance for an algorithm, but as shown by azotlichid, probably not in $O(n\log n /k)$.  
> **username_0**: Note that Guha and McGregor's pass elimination for randomized algorithms works in the opposite direction, using more space to allow fewer passes (though the additional space is large if the desired error is small).  This question asks whether by using more passes, one can reduce the space usage.  

---

## 5 answers

### Answer by username_5 on 2011-11-05. Score: 8 | Accepted answer

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](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9770), 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.

> **Comments:**
> **username_0**: M. Tompa, _Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations_, SIAM J. Comput. 11(1), 130–137.  http://dx.doi.org/10.1137/0211010  

---

### Answer by username_2 on 2011-09-26. Score: 4

This is not an answer, but I just wanted to point out that if you can solve this problem for $k = \Theta(n)$, then you solve st-connectivity in $O(\log n)$ space and $O(nm)$ time (which in the offline case you can do with probability > 1/2 by doing a random walk; but it seems a bit harder when the edges come from a stream). Very interesting question, IMO.


---

### Answer by username_3 on 2011-09-29. Score: 3

Yossi Shiloach, Uzi Vishkin. An O(log n) Parallel Connectivity Algorithm. J. Algorithms, 1982: 57~67 -- One of my favorite papers. It would be interesting if you could do it in O((nlogn/k)/p) space with p processors in $k$ rounds where each round each processor is only allowed to read in O(n/p) of the edges.

> **Comments:**
> **username_0**: Thanks for the pointer, this is an interesting paper.  The processors have common access to a data structure that is at least as large as the graph, so this doesn't help to reduce space usage.  It would be indeed be interesting if there were a way to reduce space usage by exploiting the number of rounds as well as the number of processors.  

---

### Answer by username_4 on 2011-11-09. Score: 2

Yet another non-answer: there are some papers on mapreduce-style algorithms operating on large graphs. The goal is to achieve per-machine space o(m) for dense graphs, but typically need O(n) space per machine.

theory.stanford.edu/~sergei/papers/soda10-mrc.pdf
<http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf>


---

### Answer by username_1 on 2011-11-05. Score: 1

Also not an answer, but you can decide st-connectivity in $O(n\log n/ k)$ non-deterministic space with $k$ passes. Just guess the first $n/k$ nodes of an $st$ path and check that they are connected in the first round, then continue from the last of these $n/k$ vertices and check the next $n/k$ from the $st$ path and so on.


---

