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

https://hal.inria.fr/inria-00359171
Contributor : Publications Loria <>
Submitted on : Friday, February 6, 2009 - 10:47:34 AM
Last modification on : Monday, February 15, 2021 - 10:37:18 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:57:11 PM

Files

Bousquet_new.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

413

Files downloads

294