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 4k⋅nO(1). We describe a new algorithm for Directed k-Leaf of running time 3.72k⋅nO(1). This algorithms leads to an O(1.9973n)-time algorithm for solving Directed Max Leaf on a digraph of order n. The latter algorithm is the first algorithm of running time O(γn) 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(k3)-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.