Streaming bounds from difference ramification.
András Z. Salamon · Electronic colloquium on computational complexity · 2012
In graph streaming a graph with n vertices and m edges is presented as a read-once stream of edges. We obtain an Ω(n logn) lower bound on the space required to decide graph connectivity. This improves the known bounds of Ω(n) for undirected and Ω(m) for sparse directed graphs. We develop a method of ramifying inessential differences into significant differences. For graph connectivity, this yields a crisp lower bound (with no undetermined constants) of n logn − n(log log n + 3/2) bits, via lower bounds for the Bell numbers and a pigeonhole argument. This lower bound is close to the ndlogne + 3dlogne + dlogdlognee + c upper bound for an algorithm maintaining a disjoint-partition data structure, and which is therefore essentially optimal. We also apply difference ramification to min-cut, for a crisp lower bound of n(n− 1)/2 bits.