A Polynomial Kernel For Multicut In Trees

Abstract : The MULTICUT IN TREES problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer k, whether there exists a set of k edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer. They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows. We show that MULTICUT IN TREES has a polynomial kernel.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.183-194, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00359171
Contributeur : <>
Soumis le : vendredi 6 février 2009 - 10:47:34
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08
Document(s) archivé(s) le : mardi 8 juin 2010 - 21:57:11

Fichiers

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

Identifiants

  • HAL Id : inria-00359171, version 1
  • Mot de passe :
  • ARXIV : 0902.1047

Citation

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo. A Polynomial Kernel For Multicut In Trees. Susanne Albers and Jean-Yves Marion. STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.183-194, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359171〉

Partager

Métriques

Consultations de la notice

241

Téléchargements de fichiers

167