On 2-Coverings and 2-Packings of Laminar Families

Let H be a laminar family of subsets of a groundset V. A k-cover of H is a multiset C of edges on V such that for every subset S in H, C has at least k edges that have exactly one end in S. A k-packing of H is a multiset P of edges on V such that for every subset S in H, P has at most k · u(S) edges that have exactly one end in S. Here, u assigns an integer capacity to each subset in H. Our main results are: (a) Given a k-cover C of H, there is an efficient algorithm to find a 1-cover contained in C of size ≤ k|C|=(2k - 1). For 2-covers, the factor of 2=3 is best possible. (b) Given a 2-packing P of H, there is an efficient algorithm to find a 1-packing contained in P of size ≥ |P|/3. The factor of 1/3 for 2-packings is best possible. These results are based on efficient algorithms for finding appropriate colorings of the edges in a k-cover or a 2-packing, respectively, and they extend to the case where the edges have nonnegative weights. Our results imply approximation algorithms for some NP-hard problems in connectivity augmentation and related topics. In particular, we have a 4/3-approximation algorithm for the following problem: Given a tree T and a set of nontree edges E that forms a cycle on the leaves of T, find a minimum-size subset E′ of E such that T + E′ is 2-edge connected.