Improved parameterized and exact algorithms for cut problems on trees
- Kanj, Iyad
- Lin, Guohui
- Liu, Tian
- Tong, Weitian
- Xia, Ge
- Xu, Jinhui
- Yang, Boting
- Zhang, Fenghui
- Zhang, Peng
- Zhu, Binhai
DOIAbstract
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*(rho(k)), where rho = root root 2 + 1 < 1.554 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 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 GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZ...
Add to ORKG