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].