Question

Updating an MST when an edge weight changes. You have a graph G= (V, E) with edge weights given in the graph (whatever they are). In addition, a minimum spanning tree T= (V, E′) of this graph has also been given to you. Now, say we need to increase the weight of one particular edge e. Does the MST change? If so, show how to compute the new MST in linear time. You should consider two cases: 1). when e∈E′and 2). Opposite of case 1): when e does not∈E′

Answer 1

Firstly, a simple definition of Minimum Spanning Tree(MST):

A MST is a subset of the edges E', which forms a tree connecting all the vertices present in the original graph and with the minimum possible total edge weight of all the possibles tree that can be formed by any subset of E. A graph can have multiple MSTs but all will have same total edge weight.

Now, let us consider the two cases(will discuss the case 1 after case 2):

Case 2:

e does not belong to E'

In this case as e already not present in T, therefore increasing its weight will not change T as if e was not included in T even when its weight was lower then there is no chance that T will include it after its weight is increased.

Case 1:

e belongs to E'

In this case there may be a change in T as after increasing the weight of e, there is a possibility of having some other MST whose total edge weight is lower than new total edge weight of T.

There is two approaches to get new MST,

Approach 1: Create new MST from start using Prim's algorithm which will take O( E logV).

Approach 2: (Linear time algorithm)

• Step 1: Remove e from T. This will result in two connected components.
• Step 2: Find the two components using BFS or DFS which requires time complexity of O(V+E).
• Step 3: Simply, iterate over all edges and find the edge with least weight which connects the two components. Lets say this edge as e '. This will require time complexity of O(E)
• Step 4: Include e' in T'. The resultant tree is the new MST, it may be same as T. Adding a edge in the graph requires O(1) time.

Thus, the overall time complexity of Approach 2 to obatain a new MST is O(V+E).