On Finding Directed Trees with Many Leaves
Résumé
The Rooted Maximum Leaf 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 \cite{stnum, stnumdir,LLWemb} 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 \cite{DrescherMaxLeaf}. We also show that Rooted Maximum Leaf admits an edge-quadratic kernel, improving over the vertex-cubic kernel given by Fernau et al \cite{FernauMaxLeaf}.
Domaines
Mathématique discrète [cs.DM]Origine | Fichiers produits par l'(les) auteur(s) |
---|