Improving multicut in directed trees by upgrading nodes

In this paper, we consider the network improvement problem for multicut by upgrading nodes in a directed tree T = (V, E) with multiple sources and multiple terminals. In a node based upgrading model, a node v can be upgraded at the expense of c(v) and such an upgrade reduces weights on all edges incident to v. The objective is to upgrade a minimum cost subset S ⊆ V of nodes such that the resulting network has a multicut in which no edge has weight larger than a given value D. We first obtain a minimum cardinality node multicut V_c for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in V_c. We show that our algorithm is polynomial when the number of source–terminal pairs is upper bounded by a given value.