Skip to Main content Skip to Navigation
Conference papers

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

Abstract : The 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 k-Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k-Leaf-Out-Branching, a variant of k-Leaf- Out-Branching where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the k-Leaf-Out-Branching problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for Rooted k-Leaf-Out-Branching immediately imply that the seemingly intractable k-Leaf-Out-Branching problem admits a data reduction to n independent O(k3) kernels. These two results, tractability and intractability side by side, are the first ones separating many-to-one kernelization from Turing kernelization. This answers affirmatively an open problem regarding "cheat kernelization" raised by Mike Fellows and Jiong Guo independently.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Publications Loria <>
Submitted on : Friday, February 6, 2009 - 3:11:45 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 7:05:59 PM


Files produced by the author(s)


  • HAL Id : inria-00358112, version 1



Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, et al.. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. pp.421-432. ⟨inria-00358112⟩



Record views


Files downloads