MINIMUM UPGRADING SPANNING TREE

• INSTANCE: Graph G=(V,E), three edge weight functions $d_2(e)\leq d_1(e)\leq d_0(e)$ (for each $e\in E$), where $d_i(e)$ denotes the weight of edge e if i of its endpoints are ``upgraded'', vertex upgrade costs c(v) (for each $v\in V$), a threshold value D for the weight of a minimum spanning tree.

• SOLUTION: An upgrading set $W\subseteq V$ of vertices such that the weight of a minimum spanning tree in G with respect to edge weights given by $d_W$ is bounded by D. Here, $d_W$ denotes the edge weight function resulting from the upgrade of the vertices in W, i.e., $d_W(u,v)=d_i(u,v)$ where $\vert W\cap \{u,v\}\vert=i$.

• MEASURE: The cost of the upgrading set, i.e., $c(W)=\sum_{v\in W} c(v)$.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ if the difference of the largest edge weight $D_0=\max \{ d_0(e) : e\in E\}$ and the smallest edge weight $D_2=\min \{d_2(e) : e\in E\}$ is bounded by a polynomial in $\vert V\vert$ [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 $2\ln\vert V\vert$. 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].