Minimum spanning tree such that one edge can be minimised

Question

During a computer coding exam, I have encountered such a problem.

Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the vertexes such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree by the positive number D and reduce the weight of that edge to max(0, weight-D)?

I know that Kruskal's and Prim's algorithm can all be used to solve the first part of the problem, the minimum spanning tree, and I can do it. However, I have been struggling hard for the second part, as I don't know how to minimise the weight of the tree given the number D.

Answer 1

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T,uv)$ being the sum of the edges in $T$ minus $\min(D,w(uv))$.

Let $(T, uv)$ be an optimal solution to the problem you describe, having weight $\sum_{xy \in E(T)} w(xy) - s$, where $s = \min(D, w(uv))$. There are two possibilities:

1. Every MST of $G$ contains at least one edge of weight $\ge s$.
2. At least one MST of $G$ contains no edge of weight $\ge s$.

Case 1

For case 1, we can take any MST $T'$, find an edge in it with weight at least $s$ (since we know by assumption that this exists), and produce a solution having weight at most $\sum_{xy \in E(T')} w(xy) - s$. This is at most the weight $\sum_{xy \in E(T)} w(xy) - s$ of the optimal solution $(T, uv)$, since $\sum_{xy \in E(T')} w(xy) \le \sum_{ab \in E(T)} w(ab)$ for any tree $T$ by definition of the MST. That means that for case 1, we can never miss an optimal solution by considering only MSTs.

Case 2

For case 2, consider the edge $uv$ in $T$, which has weight at least $s$. Let the vertices on one side of this edge be $A$, and the vertices on the other side $B$. By assumption, there exists an MST in which every edge has weight strictly less than $s$. In particular, this MST must contain an edge $u'v'$ between the vertex sets $A$ and $B$ having weight strictly less than $s$, since otherwise the MST would be disconnected -- a contradiction.

Suppose $w(uv) > D$. Then the original solution $(T, uv)$ has weight $X - D$, with $X$ being the weight of the entire tree $T$, while the solution formed by replacing $uv$ with $u'v'$ has weight $X - w(uv) < X - D$. This contradicts optimality of $(T, uv)$, so it must be that in fact $w(uv) \le D$, in which case both the original and new solutions have weight $X - w(uv)$. Thus the new solution has weight equal to the old solution, but now falls into case 1 above.

Wrapping up

Since there are only two possible cases for an optimal solution, and in both cases an MST can always be found that leads to a solution that is just as good, it always suffices to find an MST.

The final step is to choose an edge in the MST to minimise. Clearly it is always optimal to choose the heaviest edge in the MST.

Answer 2

We have the following lemma.

Minimality of all weights of a minimum spanning tree (MST). Let $G$ be a weighted graph with $n$ vertices. $T$ is a minimum spanning tree of $G$ with edge weights $$w_1 \le w_2 \le ... \le w_{n-1}.$$ $T'$ is a spanning tree of $G$ with edge weights: $$w'_1 \le w'_2 \le ... \le w'_{n-1}.$$ Then $w_i \le w'_i$ for all $i$.

For a proof, you can check my answer to the question Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?.

---

The solution to your problem is simple.

1. Find $T$, an MST by Kruskal's or Prim's algorithm.
2. Subtract $D$ from the heaviest edge of $T$ unless it weigh less than $D$, in which case change its weight to 0.
3. Return the total weight of $T$.

---

Proof of the correctness of the algorithm.

Consider the function $s$, $s(w)=w-D$ if $w\ge D$ and $s(w)=0$ otherwise. Then $s(w)$ is a nondecreasing function. In particular, $s(w_{n-1})\le s(w_{n-1}')$.

---

_{Note, the above answer works regardless in which way we can interpret "what is the minimum spanning tree between the vertices such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree," as discussed in the comment below that happened before this minor update of this answer, where the algorithm stays the same.}