2026-07-22T04:53:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1843 2024-03-06T10:33:12Z ddc:004 open_access

Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves Fernau, Henning Fomin, Fedor V. Lokshtanov, Daniel Raible, Daniel Saurabh, Saket Villanger, Yngve Parameterized algorithms Kernelization Out-branching Max-leaf Lower bounds 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Fernau and Fedor V. Fomin and Daniel Lokshtanov and Daniel Raible and Saket Saurabh and Yngve Villanger 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1843 urn:nbn:de:0030-drops-18437 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1843 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode