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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.421-432, 2009
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

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

Fichiers

Fernau_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00358112, version 1

Collections

Citation

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, et al.. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.421-432, 2009. 〈inria-00358112〉

Partager

Métriques

Consultations de la notice

110

Téléchargements de fichiers

241