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

Deepsix

Maybe I'm missing something -- surely G is connected so |V| <= |E| + 1? So your O(|V|) algorithm is automatically O(|E|) also, so where's the problem? Or are you saying, "I'm surprised I was able to solve it even better than the question asked me to"? – Scansion

Yes, something like that! I'm surprised it's so simple to do in O(|V|) yet it asks it to be in O(|E|) in both questions. I fear there's something I'm not seeing. Also I have to give a proof of my solution and it's obvious that if e1 is the most expensive edge on a cycle then it can't be in the MST, and that if e2 is more expensive of e1 then e2 can't be in the graph, but can't the possibility of a new path throught e1 create a MST with edges that were in G but not in the previous MST T? – Deepsix

Unless you've been told it, I don't think the property that no MST edge can be the longest edge in a cycle is "obvious". So I don't think the problem is "too easy". Re your proof question: suppose such an MST containing e1 existed. Then deleting e1 leaves 2 connected components. Because e1 was originally part of a cycle, there must be some other edge in that cycle that connects these 2 components (proving this part is left as an exercise :-P) and which has weight < w(e1). Add that edge to produce a smaller MST and thus a contradiction. So no MST containing e1 can exist. – Scansion

My previous comment only concerns the case where the cycle contains a uniquely heaviest edge. It applies even if there were or will be multiple MSTs -- no MST can ever contain that edge. But I now realise that there's more work to do if the cycle doesn't have a uniquely heaviest edge... I'm not sure then, as you can't rule out any edges for sure. Hmmm. – Scansion

I came up with the same proof as you j_random_hacker and I see no problem with it even if there are multiple edges of the same weight. What confuses me is that I think I can prove that in 2. all you need to do is add the new edge and remove the heaviest edge (any one if there are multiple) which still runs in O(|V|). – Peridotite

@Bus: Got it now! My sticking point was that it's not safe to delete a heaviest-equal edge (in the sense that there may be MSTs containing that edge) since we don't know for sure that a better edge can connect the 2 components. BUT: All MST requires is that, for any bipartition of vertices, we select 1 of the minimum-weight edges spanning that bip. So given a bip. and a cycle spanning it twice, even if both spanning edges are heaviest-equal, either can be chosen -- both will produce MSTs. So deleting a heaviest-equal edge will get you an MST, just not necessarily all of them. – Scansion

Yeah that's it. I still wonder about part 2 though. – Peridotite

@Bus: that's exactly what has been bugging me too... I totally agree with your solution of the 2nd part and it totally seems to work after a few sample tries (also I think I can demonstrate it but I may be wrong)! @j_random_hacker: thanks for all your efforts! So I think we agree that it has to work? – Deepsix

@Lynette: Since part 2 of the question asks for just a single MST, then yes, I believe it should work. Perhaps the person asking the question thought it would be necessary to consider afresh every edge spanning the 2 components that you get from deleting a heaviest edge? That would imply O(E) time. But that isn't necessary, since we're already told that we're starting from an MST. That means we already know that all of those pre-existing spanning edges are at least as heavy as the edge we will remove. So the only edge we need to consider is the newly added one. – Scansion

Isn't O(V) \in O(E)? |E| is bounded by |V|^2, so if it's in O(|V|) it's certainly in O(|E|). – Constanceconstancia

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.

Publius

Answer 2

I think a BFS would suffice. And it's complexity is O(|V| + |E|) but in a tree |E| is less than |V| so it's O(2|V|) that is O(|V|)

Gershwin

Answer 3

I believe your step Find in T the shortest path from a to b is an order E operation.

Hiroshige

No. There are |V|-1 edges in T. – Hu