On 2-coverings and 2-packings of laminar families (Q4938792)

The authors call a family \({\mathcal H}\) of subsets of a ground set \(V\) a laminar family, if any two sets of the family are either disjoint or ordered by inclusion. So the order structure is a down-tree. They call a multigraph on \(V\) a \(k\)-cover of \({\mathcal H}\) if each element of \({\mathcal H}\) intersects at least \(k\) edges in exactly one vertex (this is different from the classical set cover definition, since a set may be covered here without the supersets being covered, e.g. \(\{1\},\{1,2\},\{3\},\{4\}\) is a laminar family, and \(\{1,3\},\{2,4\}\) is a cover, but \(\{1,2\},\{3,4\}\) is not a cover). They prove that from a \(k\)-cover they can select a 1-cover which is smaller by at least the factor \({k\over 2k-1}\), and this is best possible for \(k=2\). Similarly they define a \(k\)-packing as a multigraph in which each element of \({\mathcal H}\) intersects at most \(k\) edges in exactly one vertex, and prove that from a 2-packing one can select a 1-packing which is smaller by at most the factor \({1\over 3}\), which is again best possible. For packings they also introduce capacities on the elements of \({\mathcal H}\), but treat only 2-packings. For both results they also give algorithms, and sketch a relation to an application in a connectivity augmentation problem. Finally they prove some NP-completeness results, e.g. that it is NP-complete to decide whether a 1-cover of a given laminar family of given size can be selected, if the edges have to be chosen from a cycle on \(V\). For the entire collection see [Zbl 0918.00032].