1
$\begingroup$

Let $G=(V,E)$ be an undirected graph. Given a pair of vertices $s,t \in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $t$ are connected? Is there any way to construct such an algorithm which scans the input stream only once?

Note that a semi-streaming algorithm is presented an arbitrary order of the edges of $G$ as a stream, and the algorithm can only access this input sequentially in the order it is given; it might process the input stream several times. The algorithm has a working memory consisting of $O(n\log^{O(1)}n)$ bits.

$\endgroup$
1
$\begingroup$

You cannot do it in a single pass. Consider the set of all graphs of the following form: the vertices are $\{s,t\} \cup A \cup B$, where $|A|=|B|=n/2-1$. The only allowed edges are between $s$ and $A$, between $A$ and $B$, and between $B$ and $t$.

Suppose that the algorithm is first presented with the $(A,B)$ edges, and then with the $(s,A),(B,t)$ edges. After reading the $(A,B)$ edges, it must "remember" all of them, since there could be only one $(s,A)$ edge and only one $(B,t)$ edge, in which case the answer depends on whether the corresponding vertices in $A$ and $B$ are connected. Since there are $2^{(n/2-1)^2}$ choices for the $(A,B)$ edges, the algorithm must have a memory of at least $(n/2-1)^2$ bits (since after reading the $(A,B)$ edges, it could be in any of $2^{(n/2-1)^2}$ possible states).

$\endgroup$
  • $\begingroup$ So, is there a way we can construct it with multiple passes but still getting a semi-streaming algorithm? (In other words, preserving the requirement of $O(nlog^c(n))$ bits in memory, when c>0). $\endgroup$ – KaliTheGreat Sep 13 '20 at 16:29
  • $\begingroup$ You can do it in $n$ passes using $O(n)$ memory. $\endgroup$ – Yuval Filmus Sep 13 '20 at 16:31

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.