On Finding Directed Trees with Many Leaves

The ROOTED MAXIMUM LEAF OUTBRANCHING problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there exists such a tree with at least k leaves. We use the notion of s 驴 t numbering studied in [19,6,20] to exhibit combinatorial bounds on the existence of spanning directed trees with many leaves. These combinatorial bounds allow us to produce a constant factor approximation algorithm for finding directed trees with many leaves, whereas the best known approximation algorithm has a $\sqrt{OPT}$-factor [11]. We also show that ROOTED MAXIMUM LEAF OUTBRANCHING admits an edge-quadratic kernel, improving over the vertex-cubic kernel given by Fernau et al [13].