An exact exponential-time algorithm for the Directed Maximum Leaf Spanning Tree problem

AbstractGiven a directed graph G=(V,A), the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree with as many leaves as possible. By designing a branching algorithm analyzed with Measure&Conquer, we show that the problem can be solved in time O⁎(1.9044n) using polynomial space. Allowing exponential space, this run time upper bound can be lowered to O⁎(1.8139n). We also provide an example showing a lower-bound for the running time of our algorithm