Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
An out-tree T of a directed graph D is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By l(D) and l(s)(D), we denote the maximum number of leaves over all out-trees and out-branchings of D, respectively. We give fixed parameter tractable algorithms for deciding whether l(s)(D) >= k and whether l(D) >= k for a digraph D on n vertices, both with time complexity 2(O(klogk)) center dot n(O(1)). This answers an open question whether the problem for out-branchings is in FPT, and improves on the previous complexity of 2(O(klog2k)) center dot n(O(1)) in the case of out-trees. To obtain the complexity bound in the case of out-branchings, we prove that when all arcs of D are part of at least one out-branching, l(s)(D) >= l(D)/3. The second bound we prove in this article states that for strongly connected digraphs D with minimum in-degree 3, l(s)(D) >= Theta(root n), where previously l(s)(D) >= Theta(3 root n) was the best known bound. This bound is tight, and also holds for the larger class of digraphs with minimum in-degree 3 in which every arc is part of at least one out-branching.
directed graphs fixed parameter tractable maximum leaf