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 Vc for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in Vc. We show that our algorithm is polynomial when the number of source-terminal pairs is upper bounded by a given value.