Covering a laminar family by leaf to leaf links

The Tree Augmentation Problem (TAP) is: given a tree T=(V,E)T=(V,E) and a set EE of edges (called links  ) on VV disjoint to EE, find a minimum-size edge-subset F⊆EF⊆E such that T+FT+F is 22-edge-connected. TAP is equivalent to the problem of finding a minimum-size edge-cover F⊆EF⊆E of a laminar set-family. We consider the restriction, denoted LL–TAP, of TAP to instances when every link in EE connects two leaves of TT. The best approximation ratio for TAP is 3/23/2, obtained by Even et al. (2001, 2009, 2008) [3], [4] and [5], and no better ratio was known for LL–TAP. All the previous approximation algorithms that achieve a ratio better than 22 for TAP, or even for LL–TAP, have been quite involved.For LL–TAP we obtain the following approximation ratios: 17/1217/12 for general trees, 11/811/8 for trees of height 33, and 4/34/3 for trees of height 22. We also give a very simple3/23/2-approximation algorithm (for general trees) and prove that it computes a solution of size at most min{32t,53t∗}, where tt is the minimum size of an edge-cover of the leaves, and t∗t∗ is the optimal value of the natural LP-relaxation for the problem of covering the leaf edges only. This provides the first evidence that the integrality gap of a natural LP-relaxation for LL–TAP is less than 22.