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

摘要: The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that a rooted oriented spanning tree, with at least $k$ leaves in given digraph. has recently received much attention from the viewpoint of parameterized algorithms. Here, we take kernelization based approach $k$-Leaf-Out-Branching} problem. We give first polynomial kernel for Rooted $k$-Leaf-Out-Branching}, variant where root tree searched also part input. Our cubic size and obtained using extremal combinatorics. For problem, show no possible unless hierarchy collapses third level by applying recent breakthrough result Bodlaender et al. (ICALP 2008) non-trivial fashion. However, our positive results immediately imply seemingly intractable admits data reduction $n$ independent $O(k^3)$ kernels. These two results, tractability intractability side side, are ones separating {\it many-to-one kernelization} Turing kernelization}. This answers affirmatively open regarding ``cheat kernelization'' raised Mike Fellows Jiong Guo independently.