2008/04/12 by Paul Bonsma, Bonsma, Paul, Frederic Dorn +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0804.2032
17 pages, 6 figures
arxiv created 2008/04/12 · openalex publication_date 2008/04/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ls(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 ls(D)≥ k and whether l(D)≥ k for a digraph D on n vertices, both with time complexity 2O(klog k) ⋅ nO(1). This improves on previous algorithms with complexity 2O(k3log k) ⋅ nO(1) and 2O(klog2 k) ⋅ nO(1), respectively. 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, ls(D)≥ l(D)/3. The second bound we prove in this paper states that for strongly connected digraphs D with minimum in-degree 3, ls(D)≥ Θ(√(n)), where previously ls(D)≥ Θ(√[3]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.