2008/10/27 by Henning Fernau, Fernau, Henning, Fedor V. Fomin +9 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0810.4796
openalex publication_date 2008/10/27 · arxiv created 2008/11/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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=Σp3 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(k3) 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.