Combinatorial and Algorithmic Bounds on the minimum number of leaves in a Directed Tree of a Digraph
Saket Saurabh
.
24-08-07

---

Abstract

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 of graphs that includes all strong and acyclic digraphs.

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 strong directed graph 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.

(This is a joint work with Noga Alon, Fedor V. Fomin, Gregory Gutin and Michael Krivelevich)