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].