8
$\begingroup$

I would like to check the status of the space lower bound for solving connectivity problem on stream in $p$ passes. The $\Omega(n/p)$ was stated in the literature but it seems to be for a slightly different problem. Did I miss something? Details below.

Given a graph $G$ of $n$ vertices in a stream (edges are presented one by one in a streaming manner), we want to check whether $G$ is connected. What is the minimum space an algorithm needs to solve this problem when it is allowed to read the stream for $p$ passes?

Feigenbaum et al. showed $\Omega(n)$ space for one pass algorithms for a class of problems that includes this problem (see Section 5.1) and stated that the $\Omega(n/p)$ space lower bound for connectivity was proved by Henzinger et al.. However, the only lower bound for "connectivity" problem is actually for the "$s$-$t$ connectivity" problem: given vertices $s$ and $t$, we want to check if $s$ and $t$ are in the same connected component (Theorem 6). The proof of this cannot be used for the connectivity problem since there might be many vertices incident to no edge.

So, my question is, for the specific version of connectivity that I stated, is there any lower bound known for $p$-pass stream?

$\endgroup$
6
$\begingroup$

Here's a reduction from Disjointness that might work:

Given input $n$ bit vectors $x$ and $y$, Alice and Bob want to come up with edge sets $E_1$ and $E_2$ for a graph $G$ such that $G$ is connected iff there is no index such that $x_i = y_i = 1$.

The graph $G$ will have vertex set ${0,1,\ldots,n} \times {0,1}$. For $i < n$, Alice adds the edge $((i-1,0),(i,0))$ to $E_1$ iff $x_i = 0$; similarly, Bob adds the edge $((i-1,1),(i,1))$ to $E_2$ iff $y_i = 0$. Additionally, Alice adds all the edges of the form $((i,0),(i,1))$ for $i\in {0,\ldots,n}$.

I think this graph has one connected component iff $(0,0)$ is connected to $(n,0)$, which happens iff for each $i\in{1,2,\ldots,n}$, either $x_i$ or $y_i$ is 0; that is, the two inputs are disjoint.

$\endgroup$
  • 1
    $\begingroup$ This is nice! Using your idea, we can do this as well: Construct $n$ nodes $v_1, ..., v_n$ plus $s$ and $t$. There is an edge from $s$ to $v_i$ if $x_i=0$ and from $t$ to $v_i$ if $y_i=0$. $\endgroup$ – Danu Sep 29 '10 at 4:28
  • $\begingroup$ Great! Shouldn't $s$ and $t$ also be connected by an edge? $\endgroup$ – Srikanth Sep 29 '10 at 13:29
  • $\begingroup$ Yes you're right. $s$ and $t$ should be connected by an edge. $\endgroup$ – Danu Sep 29 '10 at 15:31
5
$\begingroup$

A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.)

One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\Omega(n \log n)$ lower bound. However, since the implicit constant factor relates to the number of blocks guaranteed by Szemerédi's Regularity Lemma, it seems to end up so small as to be useless for applications.

So a more precise lower bound for the $p$-pass case is $\frac{1}{p}(n\log n - n(\log\log n + 3/2))$. I remain unconvinced that this is the true lower bound, since achieving such a bound seems unlikely -- the true dependence on $p$ seems to be weaker than an inverse proportion. However, the bound should be at least $\Omega(\frac{1}{p}n\log n)$, improving $\Omega(n/p)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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