We study the { \sc multicut on trees} and the { \sc generalized multiway Cut on trees} problems. For the { \sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{ *}(\rho^k)$, where $\rho = \sqrt{ \sqrt{ 2} + 1} \approx 1.555$ is the positive root of the polynomial $x^4-2x^2-1$. This improves the current-best algorithm of Chen et al. that runs in time $O^{ *}(1.619^k)$. For the { \sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the { \sc generalized multiway cut on trees} problem to the { \sc multicut on trees} problem, our results give a parameterized algorithm that solves the { \sc generalized multiway cut on trees} problem in time $O^{ *}(\rho^k)$, where $\rho = \sqrt{ \sqrt{ 2} + 1} \approx 1.555$ time.

Categories: cs.DS

Algorithms for Cut Problems on Trees