- INSTANCE:
Graph
*G=(V,E)*, three edge weight functions (for each ), where denotes the weight of edge*e*if*i*of its endpoints are ``upgraded'', vertex upgrade costs*c(v)*(for each ), a threshold value*D*for the weight of a minimum spanning tree. - SOLUTION:
An upgrading set
of vertices such that the weight of a minimum
spanning tree in
*G*with respect to edge weights given by is bounded by*D*. Here, denotes the edge weight function resulting from the upgrade of the vertices in*W*, i.e., where . - MEASURE:
The cost of the upgrading set, i.e.,
.

*Good News:*Approximable within if the difference of the largest edge weight and the smallest edge weight is bounded by a polynomial in [342].*Bad News:*At least as hard to approximate as MINIMUM DOMINATING SET [342].*Comment:*Variation in which the upgrading set must be chosen such that the upgraded graph contains a spanning tree in which no edge has weight greater than*D*is approximable within . In this case no additional assumptions about the edge weights are necessary. This variation of the problem is also at least as hard to approximate as MINIMUM DOMINATING SET [342].