A class of node based bottleneck improvement problems

In this paper, we consider a class of node based bottleneck improvement problems with respect to the system (V,E,F)(V,E,F), where V is a node set, E   is an edge set, and F⊆2EF⊆2E is a nonempty family of subsets of E. In the 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. For a given budget B, the objective is to upgrade a subset of nodes S ⊆ V   such that the bottleneck weight of the family FF is minimum under the constraint that the overall upgrade cost c(S) does not exceed B  . The problem includes some NP-hard cases. For the special tree-path system (V,E,F)(V,E,F), in which T = (V, E  ) is a rooted tree and FF is a set of paths from the root to the leaves, we present an O(n log n) algorithm, where n = ∣V∣. We also consider some variations of this problem. Some related complexity results and algorithms are also presented.