On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

摘要: In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and set of additional edges called links. Our goal is to find links minimum size whose addition makes it (k + 1)-edge-connected. There an approximation preserving reduction from mentioned problem case k = 1 (a.k.a. Tree or TAP) = 2 Cactus CacAP). While several better-than-2 algorithms known for TAP, CacAP only recently this barrier was breached (hence in general). As first step towards better CacAP, consider special where input cactus consists single cycle, Cycle (CycAP). This apparently simple retains part hardness general case. particular, able show that APX-hard. paper present combinatorial $\left (\frac {3}{2}+\varepsilon \right )$ -approximation CycAP, any constant e > 0. We also LP formulation with matching integrality gap: might be useful address problem.