adding an edge, Is T still a MST to the new graph?

Question

Suppose I have a minimum spanning tree $T$ in a graph $G=(V,E)$ with positive edge weights $w$. Provide an algorithm that after adding a new edge $e$ with a unique weight $w(e)$ to $G$, returns true if $T$ will still be an MST.

Answer 1

Let $n=|V|$ and $e=(x,y)$ be the new edge. Let $P$ be the unique path between $x$ and $y$ in $T$. Clearly $C = P + e$ is a cycle in $G+e$.

Let $f^* = \arg\max_{f \in P}{w(f)}$. $T$ is an MST of $G+e \iff w(e) \ge w(f^*)$.

The $\Rightarrow$ part: If $w(e) < w(f^*)$ then $T - f^* + e$ is a spanning tree of $G+e$ of cost $w(T) - w(f^*) + w(e) < w(T)$, showing that $T$ cannot be a MST of $G+e$.

The $\Leftarrow$ part: If $w(e) \ge w(f^*)$ then $e$ is one of the heaviest edges of $C$ and, by the cycle rule, there exists a MST of $G+e$ that does not include $e$. In particular, any MST of $G$ will also be an MST of $G+e$ (the converse is not true in general, but it is in your case since you also know that $w(e) > w(f^*)$ and hence no MST of $G+e$ can contain $e$).

A reasonable representation of $T$ will allow you to find $P$ (and hence $w(f^*)$ in time proportional to $|P| = O(n)$).

---

If you can preprocess $T$, then you can do better. For example you can build a lowest common ancestor (LCA) oracle in $O(n)$ time to find in constant time the LCA $z$ between $x$ and $y$. Then $w(f^*)$ will be the maximum weight between the two heaviest edges in the unique paths in $T$ from $x$ and $y$ to $z$, respectively. These edges can be found in $O(\log n)$ time after a $O(n \log n)$ time preprocessing. For each vertex $v$ of the tree, and for each $i=1,\dots,\lceil \log n\rceil$ store:

• the farthest vertex $u_v^{i}$ in the path from $v$ to the root of $T$, such that $u$ is at a distance of at most $2^i$ from $v$ in $T$; and
• the heaviest edge $e_v^{i}$ in the unique path from $v$ to $u_v^{i}$ in $T$.

To report the edge $M(x,z)$ of maximum weight between a vertex $x$ and an ancestor $z$ of $x$, let $\ell$ be the largest power of $2$ that is smaller than or equal to the distance in $T$ between $x$ and $z$. Return the heaviest edge between $e_v^i$ and $M(u_v^{i}, z)$ (if $u_v^{i} \neq z$). Notice that the distance between $u_v^{i}$ and $z$ is at most half the distance between $v$ and $z$, meaning that you will only need to look at $O(\log n)$ edges.