HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Friday, February 6, 2009 - 10:47:34 AM
Last modification on : Friday, October 22, 2021 - 3:07:28 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:57:11 PM


Files produced by the author(s)


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


Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo. A Polynomial Kernel For Multicut In Trees. STACS'2009: 26th International Symposium on Theoretical Aspects of Computer Science, Feb 2009, Freiburg, Germany. pp.183-194. ⟨inria-00359171⟩



Record views


Files downloads