A Polynomial Kernel For Multicut In Trees

Simple item page
dc.creatorBousquet, Nicolas
dc.creatorDaligault, Jean
dc.creatorThomasse, Stephan
dc.creatorYeo, Anders
dc.date2009-02-06
dc.date.accessioned2026-07-07T12:38:54Z
dc.date.available2026-07-07T12:38:54Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/0902.1047
dc.identifierhttp://arxiv.org/abs/0902.1047
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 183-194
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218925
dc.subjectDiscrete Mathematics
dc.titleA Polynomial Kernel For Multicut In Trees
dc.typetext

Files

Collections

arXiv