A New Algorithm for Finding Trees with Many Leaves

We present an algorithm that finds out‐trees and out‐branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out‐Tree and Directed Maximum Leaf Out‐Branching, respectively, and–in the case of undirected graphs–as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4 ^k nm) on directed graphs and O(poly(n)+4 ^k k ²) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2 ^{O(klog k)} poly(n) and O(poly(n)+6.75 ^k poly(k)) respectively.