2007/07/07 by Noga Alon, Fedor V. Fomin, Alon, Noga +7 · 1 citation
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 #Graph Labeling and Dimension Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0707.1095
arxiv created 2007/07/07 · openalex publication_date 2007/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The \sc Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we improve known parameterized algorithms and combinatorial bounds on the number of leaves in out-branchings. We show that \beginitemize \item every strongly connected digraph D of order n with minimum in-degree at least 3 has an out-branching with at least (n/4)1/3-1 leaves; \item if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph is O(klog k); \item it can be decided in time 2O(klog2 k)⋅ nO(1) whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. \enditemize All improvements use properties of extremal structures obtained after applying local search and of some out-branching decompositions.