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(ϵ^(−1) n log n) words. Moreover, we show our result is tight: Any algorithm with better than 2-approximation for the problem requires Ω(n^2) 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(ϵ^(−1) n^(1+1/t) log 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+n^(1+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(t logk)-approximation for SNDP using O(k n^(1+1/t)) words of space, where k is the maximum connectivity requirement