Multicut in trees viewed through the eyes of vertex cover
Venue
WADS 2011
Publication Year
2011
Authors
Jianer Chen, Jiahao Fan, Iyad A. Kanj, Yang Liu, Fenghui Zhang
BibTeX
Abstract
We take a new look at the multicut problem in trees through the eyes of the vertex
cover problem. This connection, together with other techniques that we develop,
allows us to signicantly improve the O(k^6) upper bound on the kernel size for
multicut, given by Bousquet et al., to O(k^3). We exploit this connection further
to present a parameterized algorithm for multicut that runs in time O(p^k), where p
= ( sqrt(5) + 1)/2 ~= 1.618. This improves the previous (time) upper bound of
O(2^k), given by Guo and Niedermeier, for the problem.