Minimum Spanning Tree - Changing edge weights
This post is about reconstructing the Minimum Spanning Tree(MST) of a graph when the weight of some edge changes.
You are given a weighted undirected connected graph \(G\) with vertex set \(V\) and edge set \(E\). You are also given the MST \(T\) of the graph.
Two functions are defined on this graph:
- \(Change(e,w)\) - Change the weight of edge \(e\) to \(w\).
- \(MST()\) - Output the current MST of the graph.
The objective is to efficiently process a long stream of operations which consist of both \(Change(e,w)\) and \(MST()\) functions. Assume the graph is represented as a dictionary of dictionaries like in NetworkX.
Approach 1
On seeing a \(Change(e,w)\) operation, simply modify the weight of the edge. This can be done in \(O(1)\) time.
On seeing \(MST()\), reconstruct the MST from scratch and output it. Assuming we use a simple implementation of Prim’s Algorithm, this can be done in \(O( \mid E \mid \log \mid V \mid)\) time and an extra \(O(\mid V \mid)\) to output the tree.
Approach 2
On seeing a \(Change(e,w)\), modify the weight in \(O(1)\) and also find the modified MST. Assume \(w_{old}\) is the weight of edge \(e\) before modification. Let this be the original graph. The black edges are part of the MST and the grey ones are not.
The following 4 cases will exist:
Case 1 : \(w_{old} < w\) and \(e \notin T\). The edge \(e\) is not part of the current MST \(T\) and its weight is increased. Since \(e\) is not a part of \(T\), increasing its weight will not cause the MST weight to change. So the current MST \(T\) is also the MST after modification.
Case 2 : \(w_{old} > w\) and \(e \in T\). The edge \(e\) is part of the current MST \(T\) and its weight is decreased. Since \(e\) is already a part of \(T\), decreasing its weight will decrease the weight of the MST. So the current MST \(T\) is also the MST after modification.
Case 3 : \(w_{old} > w\) and \(e \notin T\). The edge \(e\) is not part of the current MST \(T\) and its weight is decreased. This may change the current MST as there may exist a different MST with a lower weight consisting of the modified edge \(e\).
Consider the graph \(T'\) formed by adding modified edge \(e\) to MST \(T\) . Graph \(T'\) will consist of a cycle \(C\).
Cycle Property : For any cycle \(C\) in the graph, if the weight of an edge \(e\) of \(C\) is larger than the individual weights of all other edges of \(C\), then this edge cannot belong to a MST.
In this graph, the red edge was not part of the MST and its weight was decreased. The red edge together with the MST forms a graph with a cycle.
Using this property, to arrive at the modified MST, all we have to do is delete the heaviest edge of the cycle \(C\) in \(T'\). This can be done in \(O(\mid V \mid )\) time.
Case 4 : \(w_{old} < w\) and \(e \in T\). The edge \(e\) is part of the current MST \(T\) and its weight is increased. This may change the current MST as there may exist a different MST with a lower weight not consisting of the modified edge \(e\).
Consider the graph \(T'\) formed by removing modified edge \(e\) from MST \(T\) . Graph \(T'\) will consist of two disconnected trees. Assume \(e\) consists of the vertices \(a\) and \(b\). Let \(A\) be the set of vertices which are reachable from \(a\) in \(T'\) and similarly \(B\) be the set of vertices reachable from \(b\) in \(T'\). Note that \(A \cap B = \emptyset\) and \(A \cup B = V\). Consider the cut \(C = (A,B)\) of graph \(G\).
Cut Property: For any cut \(C\) of the graph, if the weight of an edge \(e\) in the cut-set of \(C\) is strictly smaller than the weights of all other edges of the cut-set of \(C\), then this edge belongs to all MSTs of the graph.
In this graph, the blue edge was part of the MST and its weight was increased. The green edges together with the blue edge form the crossing edges of the cut.
Using this property, to arrive at the modified MST, find the minimum weight crossing edge in cut \(C\) and add this to graph \(T'\). This can be done in \(O(\mid E \mid)\) time.
On seeing \(MST()\), all we have to do is output the current MST, which takes \(O(\mid V \mid)\) time.
Analysis
Intuitively, we can say that Approach 1 is useful when \(MST()\) operations are rare and Approach 2 is efficient when they are frequent.
Assume a long stream of operations consists of \(\alpha\) \(Change(e,w)\) operations and \(\beta\) \(MST()\) operations. The worst case time complexity would be
Approach 1: \(\alpha O(1) + \beta( O( \mid E \mid \log \mid V \mid) + O(\mid V \mid))\)
Approach 2: Since case 4 is the costliest. - \(\alpha (O(\mid E \mid) + O(1)) + \beta O(\mid V \mid)\)
Approach 2 is efficient when:
\[\alpha (O(\mid E \mid) + O(1)) + \beta O(\mid V \mid) < \alpha O(1) + \beta( O( \mid E \mid \log \mid V \mid) + O(\mid V \mid))\\ \alpha O(\mid E \mid) < \beta (O( \mid E \mid \log \mid V \mid)) \\ \frac{\alpha}{\beta} < O ( \log \mid V \mid)\]Can we use the cycle and cut properties to create an iterative algorithm for finding the MST of a graph. Consider this problem:
You are given a weighted undirected connected graph \(G\) with vertex set \(V\) and edge set \(E\). You are also given a tree \(T\). It is known that the tree differs from the MST of \(G\) by a few edges. Find the MST of the graph.