Algorithms for Cut Problems on Trees

2013/04/12 by Kanj, Iyad, Lin, Guohui, Liu, Tian +7
#68Q25 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1304.3653

Abstract

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^*(ρ^k), where ρ= √(√(2) + 1) ≈ 1.555 is the positive root of the polynomial x⁴-2x²-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^*(ρ^k), where ρ= √(√(2) + 1) ≈ 1.555 time.

Related

• Planar Multiway Cut with Terminals on Few Faces
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Domination and cut problems on chordal graphs with bounded leafage
• On Multiway Cut parameterized above lower bounds
• Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems