Parameterized Algorithms for Directed Maximum Leaf Problems
<|reference_start|>Parameterized Algorithms for Directed Maximum Leaf Problems: We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family $\cal L$ that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in $\cal L$. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a `spanning tree with many leaves' in the undirected case, and which is interesting on its own: If a digraph $D\in \cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves.<|reference_end|>
@article{alon2007parameterized,
    title={Parameterized Algorithms for Directed Maximum Leaf Problems},
    author={Noga Alon, Fedor Fomin, Gregory Gutin, Michael Krivelevich and Saket
  Saurabh},
    journal={arXiv preprint arXiv:cs/0702049},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702049},
    primaryClass={cs.DS cs.DM}
}