A 4/3-approximation for the maximum leaf spanning arborescence problem in DAGs

The Maximum Leaf Spanning Arborescence problem (MLSA) in directed acyclic graphs (dags) is defined as follows: Given a directed acyclic graph G and a vertex r∈V(G) from which every other vertex is reachable, find a spanning arborescence rooted at r maximizing the number of leaves (vertices with out-degree zero). The MLSA in dags is known to be APX-hard as reported by Nadine Schwartges, Spoerhase, and Wolff (Approximation and Online Algorithms, Springer, Berlin Heidelberg, 2012) and the best known approximation guarantee of 75 is due to Fernandes and Lintzmayer (J. Comput. Syst. Sci. 135: 158–174,2023): They prove that any α-approximation for the hereditary 3-set packing problem, a special case of weighted 3-set packing, yields a max{43,α}-approximation for the MLSA in dags, and provide a 75-approximation for the hereditary 3-set packing problem. In this paper, we improve upon this result by providing a 43-approximation for the hereditary 3-set packing problem, and, thus, the MLSA in dags. The algorithm that we study is a simple local search procedure considering swaps of size up to 10 and can be analyzed via a two-stage charging argument. We further provide a clear picture of the general connection between the MLSA in dags and set packing by rephrasing the MLSA in dags as a hereditary set packing problem. With a much simpler proof, we extend the reduction by Fernandes and Lintzmayer and show that an α-approximation for the hereditaryk-set packing problem implies a max{k+1k,α}-approximation for the MLSA dags. On the other hand, we provide lower bound examples proving that our approximation guarantee of 43 is best possible for local search algorithms with constant improvement size.