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 $(1+\mathrm{ln\hspace{0.17em}}2+\epsilon )$-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio $(1+\mathrm{ln\hspace{0.17em}}2+\epsilon )$ for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a $(1.5+\epsilon )$-approximation for k-SAG for any k.

Funding: This work was supported by National Science Foundation Graduate Research Fellowship Program [DGE-2140739].