FPT algorithms and kernels for the Directed k-Leaf problem

A subgraph T of a digraph D is an out-branching if T is an oriented spanning tree with only one vertex of in-degree zero (called the root). The vertices of T of out-degree zero are leaves. In the Directed Max Leaf problem, we wish to find the maximum number of leaves in an out-branching of a given digraph D (or, to report that D has no out-branching). In the Directed k-Leaf problem, we are given a digraph D and an integral parameter k, and we are to decide whether D has an out-branching with at least k leaves. Recently, Kneis et al. (2008) obtained an algorithm for Directed k-Leaf of running time 4^k ṡ n^{O (1)}. We describe a new algorithm for Directed k-Leaf of running time 3.72^k ṡ n^{O (1)}. This algorithms leads to an O (1.9973ⁿ)-time algorithm for solving Directed Max Leaf on a digraph of order n. The latter algorithm is the first algorithm of running time O (γⁿ) for Directed Max Leaf, where γ < 2. In the Rooted Directed k-Leaf problem, apart from D and k, we are given a vertex r of D and we are to decide whether D has an out-branching rooted at r with at least k leaves. Very recently, Fernau et al. (2008) found an O (k³)-size kernel for Rooted Directed k-Leaf. In this paper, we obtain an O (k) kernel for Rooted Directed k-Leaf restricted to acyclic digraphs.