Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
| dc.creator | Fernau, Henning | |
| dc.creator | Fomin, Fedor V. | |
| dc.creator | Lokshtanov, Daniel | |
| dc.creator | Raible, Daniel | |
| dc.creator | Saurabh, Saket | |
| dc.creator | Villanger, Yngve | |
| dc.date | 2008-10-27 | |
| dc.date | 2008-11-06 | |
| dc.date.accessioned | 2026-07-07T10:15:37Z | |
| dc.date.available | 2026-07-07T10:15:37Z | |
| dc.description | The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching (i.e. 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 {alonLNCS4596,AlonFGKS07fsttcs,BoDo2,KnLaRo}. In this paper we step aside and 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 polynomial hierarchy collapses to third level %$PH=Σ_p^3$ by applying a recent breakthrough result by Bodlaender et al. {BDFH08} in a non-trivial fashion. However our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable the {\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 separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding "cheat kernelization" raised in {IWPECOPEN08}. | |
| dc.identifier | https://arxiv.org/abs/0810.4796 | |
| dc.identifier | http://arxiv.org/abs/0810.4796 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/173227 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.title | Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves | |
| dc.type | text |