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.
https://hal.inria.fr/inria-00359171 Contributor : Publications LoriaConnect 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
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⟩