Minimum spanning tree such that one edge can be minimised

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.

• It looks like you are asking CCC 2017 Problem S4. However, it looks like you have changed the problem somewhat by specifying "you may subtract any one edge of your choice in the tree". If you do want to ask about the original problem, please raise a different question. – John L. Feb 16 '19 at 14:18
• Can a tree $T$ and an edge $e$ in that tree be a solution even if $T$ is not a minimum spanning tree? It might be possible to reach a lower total weight by deleting a heavy edge from a non-MST -- but it's not clear if that is allowed. – j_random_hacker Feb 16 '19 at 14:22
• @Apass.Jack Smart. That was exactly the problem I was wanting to look for a solution to, however I could not find any solution to it. I wanted to phrase the problem in technical terms. Thanks for pointing it out. – Aarony Jamesys Feb 16 '19 at 14:26

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.

• @j_random_hacker Tagging the part where you stated: "Every MST of G contains at least one edge of weight ≥s. At least one MST of G contains no edge of weight ≥s." Do you not mean D? – Aarony Jamesys Feb 17 '19 at 3:42
• @j_random_hacker And what exactly do you mean by "The vertices on one side of the edge be A"? What do you mean on one side? – Aarony Jamesys Feb 17 '19 at 3:45
• @AaronyJamesys: No, I meant $s$. Maybe $D$ could be used instead, and lead to a different proof (which might even be simpler), but is there a problem with using $s$? Do you see a mistake? – j_random_hacker Feb 17 '19 at 12:31
• @AaronyJamesys: If you delete an edge in a spanning tree, two connected components remain. The vertices in one of those components I call $A$, and the vertices in the other component I call $B$. – j_random_hacker Feb 17 '19 at 12:32

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.

• I believe that this algorithm works, but I don't yet follow your proof. For an arbitrary optimal solution $(T, uv)$ to the OP's problem, with $uv$ identifying the edge from which at most $D$ has been subtracted, how does it follow that the $(T', u'v')$ constructed by your algorithm has weight at most equal to this? – j_random_hacker Feb 16 '19 at 13:44
• @j_random_hacker, the question stated "you may subtract any one edge of your choice in the tree". The only trees I can see are the MSTs. Had the question been "you may subtract any one edge of your choice among the original edges", I would have written a different answer. – John L. Feb 16 '19 at 14:08
• I interpreted it to mean that the set of all feasible solutions is the set $\{(T, e) : T$ is a not necessarily minimum spanning tree of $G$ and $e$ is a distinguished edge in $T\}$, with the cost of a particular solution $(T, e)$ being the sum of the edges in $T$ minus $\min(D, w(e))$. Are you are suggesting that the feasible solution set consists only of minimum spanning trees? – j_random_hacker Feb 16 '19 at 14:17
• Right, but I think the difference in interpretation doesn't come down to the part you highlighted in your first comment ("you may subtract any one edge of your choice in the tree"), but rather to whether "minimum spanning tree ... provided that ..." should be parenthesised like "minimum (spanning tree ... provided that ...)" or like "(minimum spanning tree ...) provided that ...". – j_random_hacker Feb 16 '19 at 14:29
• If so, and if you mention these steps, I'll +1. (I think it's a much tidier approach than mine!) – j_random_hacker Feb 16 '19 at 15:59