zbMATH — the first resource for mathematics

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].

68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
Full Text: DOI