<p>Here's a reduction from Disjointness that might work:</p>

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

<p>The graph $G$ will have vertex set ${0,1,\ldots,n} \times {0,1}$. For $i &lt; 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}$.</p>

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

CC BY-SA 2.5
2010-09-29T04:28:30.520Z
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$.
Dan
CC BY-SA 2.5
2010-09-29T13:29:55.607Z
Great! Shouldn't $s$ and $t$ also be connected by an edge?
Srikanth
CC BY-SA 2.5
2010-09-29T15:31:45.473Z
Yes you're right. $s$ and $t$ should be connected by an edge.
Dan
CC BY-SA 2.5
2010-09-29T03:14:20.130Z
2010-09-29T03:48:08.770Z
2010-09-29T03:48:08.770Z
Srikanth
<p><a href="http://eccc.hpi-web.de/report/2012/183/" rel="nofollow noreferrer">A better lower bound when $p=1$</a> 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$.)</p>

<p>One can also apply a straightforward reduction from a <a href="http://dx.doi.org/10.1145/62212.62228" rel="nofollow noreferrer">graph connectivity communication game</a> to obtain a less explicit $\Omega(n \log n)$ lower bound.  However, since the implicit constant factor relates to the <a href="https://mathoverflow.net/questions/127773/in-szemeredis-regularity-lemma-how-many-blocks-are-in-the-partition">number of blocks guaranteed by Szemerédi's Regularity Lemma</a>, it seems to end up so small as to be useless for applications.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/8368/reducing-space-usage-of-st-connectivity-with-multiple-passes">achieving such a bound seems unlikely</a> -- 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)$.</p>

CC BY-SA 3.0
2013-05-01T11:59:50.313Z
2013-05-01T11:59:50.313Z
2017-04-13T12:57:54.777Z
András Salamon
<p>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.  </p>

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

<p><a href="http://www.cs.umass.edu/~mcgregor/papers/08-graphdistances.pdf">Feigenbaum et al</a>. 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.7290&amp;rep=rep1&amp;type=pdf">Henzinger et al.</a>. 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. </p>

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

<lower-bounds><data-streams>
Lower bound of checking graph connectivity on stream
Dan
# Lower bound of checking graph connectivity on stream

(Asked by: username_0 on 2010-09-28)

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](http://www.cs.umass.edu/~mcgregor/papers/08-graphdistances.pdf). 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.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.7290&rep=rep1&type=pdf). 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?

**Tags:** lower-bounds, data-streams

---

## 2 answers

### Answer by username_1 on 2010-09-29. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$.  
> **username_1**: Great! Shouldn't $s$ and $t$ also be connected by an edge?  
> **username_0**: Yes you're right. $s$ and $t$ should be connected by an edge.  

---

### Answer by username_2 on 2013-05-01. Score: 5

[A better lower bound when $p=1$](http://eccc.hpi-web.de/report/2012/183/) 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](http://dx.doi.org/10.1145/62212.62228) 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](https://mathoverflow.net/questions/127773/in-szemeredis-regularity-lemma-how-many-blocks-are-in-the-partition), 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](https://cstheory.stackexchange.com/questions/8368/reducing-space-usage-of-st-connectivity-with-multiple-passes) -- 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)$.


---

