Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches

We consider the connectivity augmentation problem (CAP), a classical problem in the area of survivable network design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a -edge-connected graph and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to makes the graph -edge-connected. If is odd, the problem is known to reduce to the tree augmentation problem (TAP)—i.e., is a spanning tree—for which significant progress has been achieved recently, leading to approximation factors below 1.5 (the current best factor is 1.458). However, advances on TAP have not carried over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli Proceedings of the 52nd ACM Symposium on Theory of Computing, 2020, pp. 815–825 managed to obtain the first approximation factor below 2 for CAP by presenting a 1.91-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below 1.5, based on a new analysis technique. Through these ingredients, we obtain a 1.393-approximation algorithm for CAP, and therefore also for TAP. This leads to the current best approximation result for both problems in a unified way, by significantly improving on the abovementioned 1.91-approximation for CAP and also the previously best approximation factor of 1.458 for TAP by Grandoni, Kalaitzis, and Zenklusen Proceedings of the 50th ACM Symposium on Theory of Computing, 2018, pp. 632–645. Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio of the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below 1.5.