Online Vertex Connectivity Augmentation

arXiv

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a k-vertex-connected graph F and a set of additional purchasable edges (with costs). Demand pairs (s_1,t_1),(s_2,t_2),dots(s_1,t_1),(s_2,t_2),dots then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that si and ti become (k+1)-vertex-connected in the union of F with all edges purchased so far. Our main contribution is an O((k+logn)logn)-competitive online algorithm for OVCA. We also give an offline O(k+logn)-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of F. We note that some dependence on k in the approximation ratio is necessary — i.e., the problem is hard to approximate within any polylog(n) factor independent of k — which shows a separation from the edge-connectivity setting. Finally, specializing to k=1, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an widetilde O(log^3 n)widetilde O(log^3 n)-competitive algorithm for online {1,2}{1,2}-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of 1 or 2).