| HAL-Inria | Les publications, logiciels... des scientifiques Inria |
Communication dans un congrès
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
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 has cubic size and is obtained using extremal combinatorics. For the 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 Rooted k-Leaf-Out-Branching immediately imply that the seemingly intractable 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 ones separating many-to-one kernelization from Turing kernelization. This answers affirmatively an open problem regarding "cheat kernelization" raised by Mike Fellows and Jiong Guo independently.
Littérature citée [24 références]
https://hal.inria.fr/inria-00358112
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 15:11:45
Dernière modification le : mercredi 6 décembre 2017 - 11:42:02
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:05:59
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 15:11:45
Dernière modification le : mercredi 6 décembre 2017 - 11:42:02
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:05:59
Fichiers
Fernau_new.pdf
Fichiers produits par l'(les) auteur(s)