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~(kn) space.
Our upper bound matches the known Ω(kn) 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.