# Semi-streaming algorithm for $s$-$t$ connectivity

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.

## 2 Answers

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

• 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). – KaliTheGreat Sep 13 '20 at 16:29
• You can do it in $n$ passes using $O(n)$ memory. – Yuval Filmus Sep 13 '20 at 16:31

I just wanted to add a comment to Yuval's answer but I don't have 50 reputation yet.

We don't have to distinguish all different $$2^{(n/2-1)^2}$$ subgraphs since for some subgraphs their answer to $$s$$-$$t$$ connectivity would be the same. I believe that we can use a disjoint set union data structure that solves this problem... (imagine that you are running Kruskal's algorithm on a unweighted graph, the goal is to come up with a connectivity witness shows that $$s$$ and $$t$$ are connected, you only need $$O(n\log n)$$ bits of information so store a tree.)