Tight Bounds for Vertex Connectivity in Dynamic Streams
share
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 ≥ 1, 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. This also gives a model-independent algorithm for computing a "certificate" of k-vertex-connectivity as a union of O(k^2logn) spanning forests, each on a random subset of O(n/k) vertices, which may be of independent interest.
READ FULL TEXT