6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The last claim cannot be true. If you connect $v$ with edges of very low weight to other existing nodes, then all these edges will be in the MST. $\endgroup$ – Hendrik Jan Apr 26 '16 at 0:50
3
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.