20
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – domotorp
    Commented Nov 4, 2011 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Apr 17, 2013 at 17:03

5 Answers 5

Reset to default
8
+100
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ M. Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, SIAM J. Comput. 11(1), 130–137. dx.doi.org/10.1137/0211010 $\endgroup$
    – András Salamon
    Commented Nov 7, 2011 at 15:36
  • $\begingroup$ This paper gives "an algorithm for st-connectivity that runs in simultaneously $\hspace{1.71 in}$ sub-linear space and polynomial time". ​ ​ $\endgroup$
    – user6973
    Commented Feb 4, 2017 at 4:57
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Sep 30, 2011 at 14:58
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.