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

Area of Science:

• Theoretical Computer Science
• Graph Algorithms
• Combinatorial Optimization

Background:

• The Maximum Leaf Spanning Arborescence (MLSA) problem seeks to find a spanning arborescence with the maximum number of leaves in a directed acyclic graph (dag).
• MLSA in dags is known to be APX-hard, with the best prior approximation guarantee being 7/5.
• Existing approximation algorithms for MLSA are often linked to the hereditary 3-set packing problem.

Purpose of the Study:

• To improve the approximation ratio for the MLSA problem in dags.
• To establish a tighter connection between MLSA and hereditary set packing problems.
• To analyze the performance of a simple local search algorithm for MLSA.

Main Methods:

• A local search algorithm considering swaps of size up to 10 is analyzed.
• A two-stage charging argument is employed for algorithm analysis.
• The MLSA problem is rephrased as a hereditary set packing problem to extend existing reductions.

Main Results:

• A 4/3 approximation for the MLSA problem in dags is achieved, improving the state-of-the-art.
• This result is derived from a 4/3 approximation for the hereditary 3-set packing problem.
• A generalized reduction shows that an α-approximation for hereditary k-set packing implies a max{(k+1)/k, α}-approximation for MLSA.

Conclusions:

• The developed 4/3 approximation algorithm offers the best possible guarantee for local search methods with constant improvement size.
• The study provides a clearer understanding of the relationship between MLSA and hereditary set packing.
• The findings advance the field of approximation algorithms for graph problems.