TY - JOUR

T1 - Covering a laminar family by leaf to leaf links

AU - Maduel, Yael

AU - Nutov, Zeev

PY - 2010/7/6

Y1 - 2010/7/6

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

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

KW - Approximation algorithm

KW - Edge-connectivity

KW - Edge-cover

KW - Laminar family

UR - http://www.scopus.com/inward/record.url?scp=80052349335&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2010.04.002

DO - 10.1016/j.dam.2010.04.002

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:80052349335

SN - 0166-218X

VL - 158

SP - 1424

EP - 1432

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 13

ER -