Approximation Algorithms for Steiner Connectivity Augmentation

Abstract

We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Steiner Augmentation of a Graph problem ($k$-SAG), we are given a $k$-edge-connected subgraph $H$ of a graph $G$. The goal is to augment $H$ by including links from $G$ of minimum cost so that the edge-connectivity between nodes of $H$ increases by 1. This is a generalization of the Weighted Connectivity Augmentation Problem, in which only links between pairs of nodes in $H$ are available for the augmentation. In the Steiner Connectivity Augmentation Problem ($k$-SCAP), we are given a Steiner $k$-edge-connected graph connecting terminals $R$, and we seek to add links of minimum cost to create a Steiner $(k+1)$-edge-connected graph for $R$. Note that $k$-SAG is a special case of $k$-SCAP. The results of Ravi, Zhang and Zlatin for the Steiner Tree Augmentation problem yield a $(1.5+\epsilon )$-approximation for $1$-SCAP and for $k$-SAG when $k$ is odd (SODA'23). In this work, we give a $(1+\ln 2+\epsilon )$-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio $(1+\ln 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$.

ESA 2024