Tight Bounds for Vertex Connectivity in Dynamic Streams

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\ge 1$, our algorithm with high probability outputs whether or not $G$ is $k$-vertex-connected in a single pass using $\tilde{O}(kn)$ space. Our upper bound matches the known $\mathrm{\Omega }(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 $\tilde{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^2\log n)$ spanning forests, each on a random subset of $O(n\mathrm{/}k)$ vertices, which may be of independent interest.