[Solved]: Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

Problem Detail: 

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some value. You now want to come up with a smart way to find the new MST of the graph.

My approach would be the following. Take this edge (u,v) that you changed and add it to your MST. Start from u and travel around in your MST until you end up back in u, since it is guaranteed that after inserting (u,v) you will create a cycle (MST is a tree). Then from the cycle that you found, remove the edge with the maximum weight.

I feel like this is correct but I don't know how to prove it. Can someone guide me?

Here's what I've tried:

My intuition about the problem is the following. Let's call T, the MST that we found before updating an edge (u,v). Now after updating this edge (u,v), let's just add it to our MST. What is the resulting structure? Since we connect two nodes that are part of the MST with an edge that was previously not in the MST, we create a cycle. Of course this indicates that some edge/edges need to go, since what we just created is not a valid MST. We can not remove any edges that are not part of the cycle that we just created, since this action would give us two components that are not connected. If we look at the cycle that we created, we can only remove exactly one edge and no more than that. Since we want to minimize the weight of all the edges part of the MST, we simply remove the edge with the largest weight. So in the end we get something that is definitely a spaning tree, and it is also minimal. Proving that it's spanning tree is trivial. To prove the latter, the edges that are not part of the cycle, should definitely be part of some MST (they are light edges of some cut), so it's ok to leave them there, as for the cycle removing the max weight will give a min total weight.

Asked By : jsguy

Answered By : Luke Mathieson

You are definitely on the right track. As D.W. notes, you have to prove two things:

1. The new tree is a spanning tree.
2. There is no spanning tree of lower total weight (i.e. minimality).

For (1), consider what it means to be a spanning tree:

• Every vertex must be a part of it (this is the spanning part).
• It must be a tree (i.e. a connected acyclic graph).

So with your construction, you have a starting MST $T$ for the graph $G$, and you create a new potential MST $T'$ for $G'$, which is $G$ with a single modified edge weight (which may or may not be the added edge).

• Is every vertex of $G$ (and hence $G'$) in $T'$?
• Is $T'$ connected?

For (2), you want to show that there's no other tree that is better. Proofs of this kind are normally done by contradiction. So start by assume there is a tree $R$ that is a spanning tree of $G'$ and has lower weight than $T'$, what would this imply?

In thinking about this consider what it means for $R$ to be different, and what this would imply for $T$, the original MST.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42766