Problem Detail: 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?
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’$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/56486
Related
