Computer Science Asked by KaliTheGreat on November 30, 2020

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(nlog^{O(1)}n)$ bits.

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

Answered by Yuval Filmus on November 30, 2020

1 Asked on November 28, 2021 by user2207686

0 Asked on November 28, 2021

combinatorics formal languages regular languages strings word combinatorics

2 Asked on November 28, 2021

church turing thesis mu recursion turing completeness turing machines

0 Asked on November 25, 2021

2 Asked on November 25, 2021 by hish

finite automata pumping lemma regular expressions regular languages

5 Asked on November 23, 2021 by stephen-mwangi

1 Asked on November 23, 2021 by judy-l

3 Asked on November 21, 2021

functional programming higher order logic lambda calculus polymorphisms programming languages

0 Asked on November 21, 2021 by user3862410

algorithm analysis algorithms coding theory order theory ordering

1 Asked on November 21, 2021

2 Asked on November 17, 2021 by ocram

1 Asked on November 17, 2021 by user123521

1 Asked on November 17, 2021 by dshri

0 Asked on November 13, 2021 by northerner

1 Asked on November 11, 2021 by pragya

1 Asked on November 11, 2021 by yuezato

1 Asked on November 8, 2021 by john-flemin

2 Asked on November 5, 2021 by vinay-varahabhotla

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir