Approximation Algorithms for Steiner Connectivity Augmentation

We consider connectivity augmentation problems in the Steiner setting. In the Steiner Augmentation of a Graph problem (k-SAG), we are given a k-edge-connected graph H, which we seek to augment by including links of minimum cost so that the edge connectivity between nodes of H increases by 1. Unlike the standard Connectivity Augmentation Problem, links to Steiner nodes outside H are available for the augmentation. If H is not assumed to be globally k-edge connected but rather Steiner k-edge connected on some set of terminals R, then we obtain the more general Steiner Connectivity Augmentation Problem (k-SCAP). We give a Formula: see text-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio Formula: see text for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a Formula: see text-approximation for k-SAG for any k. Funding: This work was supported by National Science Foundation Graduate Research Fellowship Program DGE-2140739.