A $$\nicefrac {4}{3}$$-approximation for the maximum leaf spanning arborescence problem in DAGs
针对有向无环图中的最大叶子生成树问题，提出一个4/3近似算法，通过局部搜索和两阶段计费分析，并证明该界对局部搜索算法是最优的。
Abstract 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\in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 $$\frac{7}{5}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>7</mml:mn> <mml:mn>5</mml:mn> </mml:mfrac> </mml:math> is due to Fernandes and Lintzmayer (J. Comput. Syst. Sci. 135: 158–174,2023): They prove that any $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> -approximation for the hereditary 3- set packing problem , a special case of weighted 3-set packing, yields a $$\max \{\frac{4}{3},\alpha \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>max</mml:mo> <mml:mo>{</mml:mo> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mi>α</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> -approximation for the MLSA in dags, and provide a $$\frac{7}{5}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>7</mml:mn> <mml:mn>5</mml:mn> </mml:mfrac> </mml:math> -approximation for the hereditary 3-set packing problem. In this paper, we improve upon this result by providing a $$\frac{4}{3}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> </mml:math> -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 $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> -approximation for the hereditary k - set packing problem implies a $$\max \{\frac{k+1}{k},\alpha \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>max</mml:mo> <mml:mo>{</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>k</mml:mi> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mi>α</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> -approximation for the MLSA dags. On the other hand, we provide lower bound examples proving that our approximation guarantee of $$\frac{4}{3}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> </mml:math> is best possible for local search algorithms with constant improvement size.