When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1843
URN: urn:nbn:de:0030-drops-18437
URL: https://drops.dagstuhl.de/opus/volltexte/2009/1843/
 Go to the corresponding LIPIcs Volume Portal

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

 pdf-format:

### Abstract

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 also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics.

For the {\sc $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 {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding cheat kernelization'' raised by Mike Fellows and Jiong Guo independently.

### BibTeX - Entry

@InProceedings{fernau_et_al:LIPIcs:2009:1843,
author =	{Henning Fernau and Fedor V. Fomin and Daniel Lokshtanov and Daniel Raible and Saket Saurabh and Yngve Villanger},
title =	{{Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves}},
booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
pages =	{421--432},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-09-5},
ISSN =	{1868-8969},
year =	{2009},
volume =	{3},
editor =	{Susanne Albers and Jean-Yves Marion},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},