Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh & Yngve Villanger
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.