# big data – Semi-streaming algorithm for \$s\$-\$t\$ connectivity

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