Updating a Minimum spanning tree when a new edge is inserted

Question

I've been presented the following problem in University:

Let G = (V, E) be an (undirected) graph with costs c_e >= 0 on the edges e ∈ E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v, t_v ∈ V with cost c.

1. Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.
2. Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree.

This is the solution I found:

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

It seems to work but I can easily make this run in O(|V|) time, while the problem asks O(|E|) time. Am I missing something?

By the way we are authorized to ask for help from anyone so I'm not cheating :D

Answer 1

You've got the right idea, though you can do better than BFS for the shortest-path search if you store the tree the right way.

Say one node r in T is the root (you can pick any node and BFS from there to generate this structure if you have marked the tree edges in a matrix or adjacency-list graph structure), and each other node has a parent pointer and a depth count. To find the shortest path between a and b in T:

1. Let a be the 'deeper' node; swap if needed.
2. Traverse the parent links from a until either b or r is reached, storing the path traversed, marking the nodes visited.
3. If you reach b, the shortest path is as traversed.
4. If you reach r, then also traverse from b to the root; if you reach node reached in the traversal from a to r, stop. Join the two where they meet and you have the shortest path in T.

Proof of the validity of this algorithm is left as an exercise to the reader. This is O(|V|) like BFS, but will also generally be faster. Only a few MST configurations would actually require O(|V|) time in practice. Of course, generating the parent-link tree takes O(|V|) time to begin with, so this only help in some circumstances, such as if you use an MST-building algorithm that naturally creates this structure in the process of determining the MST.

As another commenter said, note that if there is a MST for a graph it is connected, so |V| <= |E| and thus O(|V|) < O(|E|).

Also, to fix the tree in O(|V|) time, if needed, simply find the longest edge on the cycle and remove it, replacing it with the new edge. Doing this efficiently with a parent-link MST is also an exercise for the reader.