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

Glencora Borradaile, Claire Mathieu, Theresa Migler

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)$ o…