Lower bounds for testing digraph connectivity with one-pass streaming algorithms

Abstract

In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex $s$ to all vertices - each require a working memory of $\Omega (\epsilon m)$ on a graph with $m$ edges to be determined correctly with probability greater than $(1+\epsilon )/2$.

Added some references to previous work, removed the part of the result that was already known before, and changed the label of the result from "Theorem" to "Lemma"