Online Vertex Connectivity Augmentation
- Yaowei Long ,
- Sepideh Mahabadi ,
- Jakub Tarnawski
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 -vertex-connected graph and a set of additional purchasable edges (with costs). Demand pairs then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that and become -vertex-connected in the union of with all edges purchased so far. Our main contribution is an -competitive online algorithm for OVCA. We also give an offline -approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of . We note that some dependence on in the approximation ratio is necessary — i.e., the problem is hard to approximate within any factor independent of — which shows a separation from the edge-connectivity setting. Finally, specializing to , our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an -competitive algorithm for online -VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of or ).