A Polynomial Kernel for Multicut in Trees

Nicolas Bousquet, Jean Daligault, Stephan Thomasse & Anders Yeo
The {\sc 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 (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.