A 43-approximation for the maximum leaf spanning arborescence problem in DAGs

• 成果类型: Article; Early Access
• 署名作者: Neuwohner, Meike
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02233-0
• 发表日期: 2025
• 关键词: tree; approximation

摘要

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 is an element of 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 MLSAin dags is known to be APX-hard as reported byNadine Schwartges, Spoerhase, andWolff (Approximation and OnlineAlgorithms, Springer, Berlin Heidelberg, 2012) and the best known approximation guarantee of 7/5 is due to Fernandes and Lintzmayer (J. Comput. Syst. Sci. 135: 158-174,2023): They prove that any alpha-approximation for the hereditary 3-set packing problem, a special case of weighted 3-set packing, yields a max{4/3, alpha}-approximation for the MLSA in dags, and provide a 7/5 -approximation for the hereditary 3-set packing problem. In this paper, we improve upon this result by providing a 4/3 -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 a-approximation for the hereditary k-set packing problem implies a max{k+1/k, alpha}-approximation for theMLSA dags. On the other hand, we provide lower bound examples proving that our approximation guarantee of 4/3 is best possible for local search algorithms with constant improvement size.