Algorithms for Cut Problems on Trees

We study the multicut on trees and the generalized multiway cut on trees problems. For the multicut on trees problem, we present a parameterized algorithm that runs in time O^∗ (ρ^k), where ρ = _ √ 2 + 1 ≈ 1.555 is the positive root of the polynomial x⁴ - 2^x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O^∗ (1.619^k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O^∗ (ρ^k). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant.