Question

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G. Design an algorithm to update the minimum spanning tree when the weight of a single edge is increased. 

The input to your algorithm should be the edge e and its new weight: your algorithm should modify T so that it is still a MST. Analyze the running time of your algorithm and prove its correctness.

Answer 1

The main result to use for designing an algorithm to update the minimum spanning tree (MST) when the edge weight of a single edge is increased is the following:
"The minimum weight edge across any cut must be part of MST"

Use this in the following way:
Let G=(V,E) be the graph with T being the given MST. Let e=(u,v) be the edge for which weight is increased. Let the number of vertices in the graph be and the number of edges be .

If the edge e=(u,v) is not in T, then after increasing the weight of this edge, the MST will not change. To see why, consider the run of Kruskal's algorithm again on this new graph. The given edge was chosen to not be in the MST. This means that this edge was not a minimum weight edge across some cut. The same will hold after the weight of the edge has increased, as it can not become the minimum edge across a cut after increasing weight. Therefore, there's nothing to do and T is still the MST.

If e=(u,v) is in T, then do the following. Consider the cut that is formed by removing from T. Compute the vertices that are reachable from and the vertices reachable from in the two tree remaining after removing this edge. This can be done by running a BFS from these two vertices while using edges only from T. Let the tree reachable from be and that from be .

Find the minimum weight edge across this cut by going over all edges such that they have one endpoint in and the other in . Let this edge be . Add it to MST and remove from it. The new tree formed i.e. will be the new MST.

To argue the correctness of the algorithm, note that is a minimum weight edge across the cut being considered, therefore it must be in MST. As for the edges already in T except for , their weight has not changed, therefore they will remain the minimum weight edge across their respective cuts. This implies that edges other than e will remain in the tree as it is. Hence, the new tree formed must be a MST.

To argue the running time, note that the BST to find the edges in the two subtrees will take O(n) time, while enumerating over all edges will take O(m) time. Hence the total time is O(n+m).

Comment in case of any doubts.