Tight Bounds for Vertex Connectivity in Dynamic Streams
Authors:
Sepehr Assadi, Vihan Shah.
Abstract:
We present a streaming algorithm for the vertex connectivity problem in dynamic streams with a
(nearly) optimal space bound: for any n-vertex graph G and any integer k > 0,
our algorithm with high probability outputs whether or not G is k-vertex-connected in a single
pass using O~(k n) space.
Our upper bound matches the known Ω(k n) lower bound for this problem even in insertion-only streams—which we extend to multi-pass algorithms in this paper—and closes one of the last remaining gaps
in our understanding of dynamic versus insertion-only streams. Our result is obtained via a novel analysis of the previous best dynamic streaming algorithm of Guha, McGregor, and Tench [PODS 2015] who obtained an
O~(k^2 n) space algorithm for this problem.
Conference version:
[PDF]