The following technical report is available from http://aib.informatik.rwth-aachen.de:

A New Algorithm for Finding Trees with Many Leaves Joachim Kneis, Alexander Langer, Peter Rossmanith AIB 2008-15

We present an algorithm that finds trees with at least k leaves in undirected and directed graphs. These problems are known as Maximum Leaf Spanning Tree for undirected graphs, and, respectively, Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Spanning Out-Tree in the case of directed graphs.

The run time of our algorithm is O(poly(|V|) + 4^k k^2) on undirected graphs, and O(4^k |V| |E|) on directed graphs. Currently, the fastest algorithms for these problems have run times of O(poly(n) + 6.75^k poly(k)) and 2^{O(k log k)} poly(n), respectively.