Kernel(s) for problems with no kernel

Abstract

The 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 k -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k -Leaf-Out-Branching, a variant of k -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with O ( k 3 ) vertices is obtained using extremal combinatorics. For the k -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly . However, our positive results for Rooted k -Leaf-Out-Branching immediately imply that the seemingly intractable k -Leaf-Out-Branching problem admits a data reduction to n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization . This answers affirmatively an open problem regarding “cheat kernelization” raised by Mike Fellows and Jiong Guo independently.