Lower bound of checking graph connectivity on stream

Question

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?

Answer 1

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.

Answer 2

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)$.