Finding MST after adding a new vertex

Question

Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new graph in $O(|V|\cdot \log |V|)$.

Basically, the idea is using Prim algorithm, only putting in priority-queue the edges of $T$ plus the new edges.

I don't fully understand the reason it works. Why it has to be a minimum spanning tree? What about a case where the heaviest edge in $T$ is $9$ for example, and we have other edges in the graph (And not in $T$) with the same weight?

It was also claimed that $|V|-1$ of the edges must be from the old graph and the other one will be one of the new - I'm not sure it's even correct. What do you think?

Answer 1

As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$.

For the sake of simplicity, let's assume that $T$ is the unique MST. (This is not required, but it is easier to reason about correctness in this case.)

Now think about what would happen if we ran Prim's on the full graph after the new vertex and edges had been added. We would start with an arbitrary single vertex and successively add edges that are adjacent to the growing tree.

Here's the key idea: each edge that is added by Prim's on the full graph will either belong to $T$, or to $E'$. If at some step we tried to add an edge in $E$ but not in $T$, then $T$ would not be a (unique) MST.

Since we know that regular Prim's would only add edges from $E'$ and $T$, these are the only edges that need to be added to the priority queue.

As Hendrick Jan said in comments, it is certainly not the case that $|V|-1$ of the edges must be from the old graph, for all of the new edges may be less than the minimum weight edge in the old graph, in which case the MST would include all of the edges in $E'$.

Answer 2

(This is a copy of the answer to the same question on the general StackOverflow)

There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is faster than Prim or Kruskal. Probably the most neat algorithm proposed in the paper below [1] uses just one cleverly designed DFS call. It is strange that people do not know this algorithm, although it can be explained by its date: it was proposed long before both Prim and Kruskal.

That algorithm is based on an observation that the new MST shall consist of edges that either belong to the old MST or are adjacent to the newly inserted vertex (let's denote it z as in the cited paper). Furthermore, it constructs the new MST recursively while performing a depth-first search on the old MST. So its running time is proportional to the number of edges in the old MST, plus the number of edges adjacent to z, hence O(n). The way it does it is detailed below.

• While traversing the old MST, the algorithm writes out the edges that definitely belong to the new MST.
• When exiting a vertex w, the algorithm has written out all the edges that belong to an MST of the subtree of w plus the vertex z, except its heaviest edge. The fate of this heaviest edge is to be determined later, because the subtree may be connected to the rest of the graph either via z or via some old edge - so the algorithm returns this heaviest edge from the call to DFS.
• To process a w, it starts by adding the edge wz to the graph, but as it is also the heaviest edge at that moment, it is not yet written out, but kept in a separate variable t. Then it iterates over the children of of w, if any, and runs DFS recursively on each of them. Let the current child be r, and let the DFS call on it return an edge t'. One of rw and t' has to be in the final MST - otherwise some of the vertices in the subtree of r will never get connected - so the cheapest one gets written out. The heaviest one may still survive, but first it needs to compete with t: it replaces t only if t is heavier, otherwise keeping t is better. Then the algorithm continues with the next child, or, if there are no more children, returns t.
• When the algorithm exits from the root vertex of the old MST, there is no other choice than to add the just-returned edge to the new MST, thus completing the run.

Using Python as pseudocode, the algorithm can be written down as follows:

def update_mst(w, z):
    visited(w) = True
    t = edge(w, z)
    for r in old_mst_adjacent(w):
        if not visited(r):
            tt = update_mst(r, z)
            rw = edge(r, w)
            if cost(rw) < cost(tt):
                add_to_new_mst(rw)
                t = min(t, tt)
            else:
                add_to_new_mst(tt)
                t = min(t, rw)
    return t
  

Note that [1] uses a global variable instead of returning the heaviest edge from the recursive call, but the presented way is, I think, somewhat cleaner to the modern programmers.

[1] Francis Chin and David Houck. 1978. Algorithms for Updating Minimal Spanning Trees. J. Comput. System Sci. 16 (1978), 333–344.