Streaming Algorithms for Network Design

We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r (uv) for each u, v V. The objective is to find a min-weight subgraph H G s. t. , for every pair of u, v V, u and v are r (uv) -edge/vertex-connected. Recent work by Jin et al. JKMV24 obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). We consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. * We provide a general framework for solving connectivity problems in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP, we provide an O (tk) -approximation in O (k^1-1/tn^1 + 1/t) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O (t) -approximation where is the integrality gap of the natural cut-based LP relaxation. When applied to the EC-SNDP, our framework provides an O (t) -approximation in O (k^1/2-1/ (2t) n^1 + 1/t + kn) space, improving the O (t k) -approximation of JKMV24 using O (kn^1+1/t) space; this also extends to element-connectivity SNDP. * We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected subgraph G, and the weighted links L arrive in the stream; the goal is to store the min-weight set of links s. t. G L is (k+1) -vertex-connected. We obtain O (1) approximations in near-linear space for k = 1, 2. Our result for k=2 is based on SPQR tree, a novel application for this well-known representation of 2-connected graphs.