On finding directed trees with many leaves.

*(English)*Zbl 1273.68162
Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 86-97 (2009).

Summary: 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 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{\text{OPT}}\)-factor. We also show that ROOTED MAXIMUM LEAF OUTBRANCHING admits an edge-quadratic kernel, improving over the vertex-cubic kernel given by H. Fernau et al. [LIPICS – Leibniz International Proceedings in Informatics 3, 421–432 (2009; Zbl 1236.68087)].

For the entire collection see [Zbl 1178.68005].

For the entire collection see [Zbl 1178.68005].