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 E E of edges (called links ) on V V disjoint to E E , find a minimum-size edge-subset F?E F ? E such that T+F T + F is 2 2 -edge-connected. TAP is equivalent to the problem of finding a minimum-size edge-cover F?E F ? E of a laminar set-family. We consider the restriction, denoted LLTAP, of TAP to instances when every link in E E connects two leaves of T T . The best approximation ratio for TAP is 3/2 3 / 2 , obtained by Even etal. (2001, 2009, 2008) [3], [4]and[5], and no better ratio was known for LLTAP. All the previous approximation algorithms that achieve a ratio better than 2 2 for TAP, or even for LLTAP, have been quite involved. For LLTAP we obtain the following approximation ratios: 17/12 17 / 12 for general trees, 11/8 11 / 8 for trees of height 3 3 , and 4/3 4 / 3 for trees of height 2 2 . We also give a very simple3/2 3 / 2 -approximation algorithm (for general trees) and prove that it computes a solution of size at most min { 3 2 t , 5 3 t ? } , where t t 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 LLTAP is less than 2 2 .
laminar family edge-cover approximation algorithm edge-connectivity