Update minimum spanning tree if edge is added

Question

I have a possible solution for the following question, but not sure if correct:

Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly.

An edge is added to G to produce a new graph. Give an algorithm that uses T to find a minimum spanning tree for the new graph in O(|V|) time.

My algorithm:

for each vertex do
   if smallest edge not in T then
      replace this edge with existing edge in T
      break
   end if
end for

I do not have much experience in writing pseudocode, so my algorithm might be over-simplified or incorrect. Please correct me if I am wrong. Thanks!

Answer 1

Don't know if your algorithm is correct, but it doesn't seem O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in O(1).

The most usual way to add an edge e=(u, v) into a MST T is:

• Run a BFS in T from u to v to detect the edge with maximum value in that path. (O(|V|))
• If that edge's weight is greater than the weight of the edge you're trying to add, remove that old edge and add the new one. Otherwise, do nothing, because the new edge would not improve the MST. (O(1)).

The rationale behind this solution is that simply adding the edge into T would create exactly one cycle, and to restore the MST property you have to remove the edge with maximum value from that cycle.

Answer 2

Yes, your algorithm seems to be correct. I would amend your pseudocode to clarify that "if smallest incident edge not in T then" so that your new algorithm is this:

for each vertex do
   if smallest incident edge not in T then
      replace this edge with existing edge in T
      break
   end if
end for

Proof by contradiction:

There exist two cases: the new edge is either in the MST or it isn't. For the case that it is: Suppose that the algorithm does not replace an edge in T. This must mean that all edges in T are smaller than other edges that are incident on the same vertex. This is a contradiction because that means the new edge is not in the MST of T.

The proof for the other case is a trivially similar proof by contradiction.