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 k-edge-connected graph G=(V,E) and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to G makes the graph (k+1)-edge-connected. If k is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP)—i.e., G is a spanning tree—for which significant progress has been achieved recently, leading to approximation factors below 1.5 (the currently best factor is 1.458). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) 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.