Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\' a, SIAM J. Comput., 10 (1981), pp. 270-283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290-306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815-825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632-645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) - ₁₁₂₀ ⁹⁶⁷ + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP'14, Springer, Berlin, 2014, pp. 800-811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we ``open the box"" and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.