A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
Guy Kortsarz, Zeev Nutov · ACM Transactions on Algorithms · 2015
The Tree Augmentation Problem (TAP) is as follows: given a connected graph G =( V , ε ) and an edge set E on V , find a minimum size subset of edges F ⊆ E such that ( V , ε ∪ F ) is 2-edge-connected. In the conference version [Even et al. 2001] was sketched a 1.5-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. The first part [Even et al. 2009] only proved ratio 1.8. An attempt to simplify the second part produced an error in Even et al. [2011]. Here we give a correct, different, and self-contained proof of the ratio 1.5 that is also substantially simpler and shorter than the previous proofs.