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 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 (^-1 n^1+1/t n) for integer t, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on 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 k) -approximation for SNDP using O (kn^1+1/t) words of space, where k is the maximum connectivity requirement.