Finding an MST with one adding and removing vertex operation

Question

I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin V(G)$, I have to calculate the MST of $$G^{'}((V(G) \backslash \{v_i\})\cup\{v_j\}, (E\backslash\{(v_i, v_k): v_k \in V(G)\})\cup\{(v_k, v_j): v_k \in V(G^{'})\}),$$ i.e, the graph $G$ with the vertex $v_j$ (and edges from $v_j$ to every other vertex) and without the vertex $v_i$ (and its respective edges). To solve this, we can apply some well-known MST algorithms, such as Prim's, Kruskal's, Borukva's algorithm. Neverthless, if we do this we would not use the already existing MST $T$, i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $T$.

There are two similar questions to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).

The vertices are points in $\mathbb{R}^2$, and the weight on each edge is the Euclidean distance between the two points.

• D.W.: Possibly useful: cs.stackexchange.com/q/124369/755, cs.stackexchange.com/q/91539/755, cs.stackexchange.com/q/56486/755.
• Kai: Why would the new MST necessarily share a single edge with what's left of the previous one after removing $v_i$? Consider $V = \{(0,0),(0,3),(4,0)\}$ and replace $(4,0)$ with $(0,1)$.
• Matheus Diógenes Andrade: I'm sorry I didn't get your point.
• Matheus Diógenes Andrade: Thank you everyone for the help.

Answer 1

After long hours facing this problem, with my advisor help, we could solve this problem in $O(|E(G^{'})| log\text{ }C)$ time complexity by using one iteration of the Boruvka's algorithm, where $C$ is the number of connected components of $G^{''} (V(G^{'}), T\backslash \{(v_k, v_i): v_k \in V(G^{'})\})$, i.e., the number of connected components of the MST $T$ by removing $v_i$ (and edges from $v_i$ to every other vertex in $T$) plus one (due to the inserted vertex $v_j$).

Note that, this solution might have $O(|E(G^{'})| log\text{ }|V(G^{'})|)$ time complexity if the removing of $v_i$ in $T$ (and edges from $v_i$ to every other vertex in $T$) lead to a totally disconnected graph. Also, note that, this solution has $\Omega(|E(G^{'})|)$ if C is equals to 3.