On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum cardinality whose addition to the graph makes it \((k+1)\)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case \(k=1\) (a.k.a. the Tree Augmentation Problem or TAP) or \(k=2\) (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, nothing better is known for CacAP (hence for k-Connectivity Augmentation in general).