Let T = (V, E) be an undirected tree, in which each edge is associated with a non-negative cost, and let {s 1 , t 1 },..., {s k , t k } be a collection of k distinct pairs of vertices. Given a requirement parameter t   0. This result is achieved by introducing problem-specific insight to the general framework of using the Lagrangian relaxation technique in approximation algorithms. Our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. We provide a Lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. Finally, we present a new 2-approximation algorithm for multicut on a tree, based on LP-rounding.
['Asaf Levin', 'Danny Segev']
Partial multicuts in trees