Streaming Algorithms for Connectivity Augmentation

We study the k-connectivity augmentation problem (k-CAP) in the single-pass streaming model. Given a $(k-1)$-edge connected graph $G=(V,E)$ that is stored in memory, and a stream of weighted edges L with weights in \0,1,,W\, the goal is to choose a minimum weight subset L'⊆ L such that G'=(V,E∪ L') is k-edge connected. We give a (2+ε)-approximation algorithm for this problem which requires to store O(ε⁻¹ nlog n) words. Moreover, we show our result is tight: Any algorithm with better than $2$-approximation for the problem requires Ω(n²) bits of space even when $k=2$. This establishes a gap between the optimal approximation factor one can obtain in the streaming vs the offline setting for k-CAP. We further consider a natural generalization to the fully streaming model where both E and L arrive in the stream in an arbitrary order. We show that this problem has a space lower bound that matches the best possible size of a spanner of the same approximation ratio. Following this, we give improved results for spanners on weighted graphs: We show a streaming algorithm that finds a (2t-1+ε)-approximate weighted spanner of size at most O(ε⁻¹ n1+1/tlog n) for integer t, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on log W. Using our spanner result, we provide an optimal $O(t)$-approximation for k-CAP in the fully streaming model with O(nk + n1+1/t) words of space. Finally we apply our results to network design problems such as Steiner tree augmentation problem (STAP), k-edge connected spanning subgraph (k-ECSS), and the general Survivable Network Design problem (SNDP). In particular, we show a single-pass O(tlog k)-approximation for SNDP using O(kn1+1/t) words of space, where k is the maximum connectivity requirement.