The 2-3-Set Packing problem and a 4/3-approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags
share
The weighted 3-Set Packing problem is defined as follows: As input, we are given a collection 𝒮 of sets, each of cardinality at most 3 and equipped with a positive weight. The task is to find a disjoint sub-collection of maximum total weight. Already the special case of unit weights is known to be NP-hard, and the state-of-the-art are 4/3+ϵ-approximations by Cygan and Fürer and Yu. In this paper, we study the 2-3-Set Packing problem, a generalization of the unweighted 3-Set Packing problem, where our set collection may contain sets of cardinality 3 and weight 2, as well as sets of cardinality 2 and weight 1. Building upon the state-of-the-art works in the unit weight setting, we manage to provide a 4/3+ϵ-approximation also for the more general 2-3-Set Packing problem. We believe that this result can be a good starting point to identify classes of weight functions to which the techniques used for unit weights can be generalized. Using a reduction by Fernandes and Lintzmayer, our result further implies a 4/3+ϵ-approximation for the Maximum Leaf Spanning Arborescence problem (MLSA) in rooted directed acyclic graphs, improving on the previously known 7/5-approximation by Fernandes and Lintzmayer. By exploiting additional structural properties of the instance constructed in their reduction, we can further get the approximation guarantee for the MLSA down to 4/3. The MLSA has applications in broadcasting where a message needs to be transferred from a source node to all other nodes along the arcs of an arborescence in a given network.
READ FULL TEXT