Update minimum spanning tree with modification of edge

Question

A graph (positive weight edges) with a MST If some edge, e is modified to a new value, what is the best way to update the MST without completely remaking it. I think this can be done in linear time. Also, it seems that I would need a different algorithm based on whether 1) e is already a part of the MST and 2) whether the new edge, e is larger or smaller than the original

Answer 1

There are 4 cases:

1. Edge is in MST and you decreasing value of edge:
   Current MST is still MST

2. Edge is not in MST and you decreasing value of edge:
   Add this edge to the MST. Now you've got exactly 1 cycle.
   Based on cycle property in MST you need to find and remove edge with highest value that is on that cycle. You can do it using dfs or bfs. Complexity O(n).

3. Edge is in MST and you increasing its value of edge:
   Remove this edge from MST. Now you have 2 connected components that should be connected. You can calculate both components in O(n) (bfs or dfs). You need to find edge with smallest value that connects these components. Iterate over edges in ascending order by their value. Complexity O(n).

4. Edge is not in MST and you increasing its value of edge:
   Current MST is still MST