2026-07-20T14:48:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1824 2024-03-06T10:33:09Z ddc:004 open_access

A Polynomial Kernel for Multicut in Trees Bousquet, Nicolas Daligault, Jean Thomasse, Stephan Yeo, Anders 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 {\sc Multicut In Trees} has a polynomial kernel. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bousquet and Jean Daligault and Stephan Thomasse and Anders Yeo 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1824 urn:nbn:de:0030-drops-18247 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1824 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode