Connectivity vs. reachability

We consider the problem of the relative complexity of the connectivity and reachability (s-t-connectivity) problems, in a model resembling the one used for graph properties. In our model an oracle answers queries about edge-induced subgraphs, and we count the number of queries made. The main result is that in order to determine whether t is reachable from s one has to ask Ω(n2) questions about the connectivity of edge-induced subgraphs. For non-adaptive strategies we show that n 2 questions are necessary for n≥6. Several other results are included.

Authors

• M. Chrobak
• H. Karloff
• T. Radzik

Keywords

No keywords are indexed for this paper.