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

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.

• Have you tried something ? Basically, in a tree, there is a unique path between any pair of nodes. Here you add a new potential path between $a$ and $b$. Is it worth replacing any edge of the previous path $a$ to $b$ by this one to reduce the total weight of the tree ? – Optidad Nov 22 '19 at 16:15

## 1 Answer

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.

• what is the cycle rule? that the part i couldn't get in my proof. – Amir Mor Nov 23 '19 at 15:32
• Let $C$ be a cycle of $G$ and let $e$ be and ege of $C$. If $w(e) > \max_{f \in C} w(f)$, then $e$ does not belong to any MST of $G$. (This is the version stated here). If $w(e) \ge \max_{f \in C} w(f)$, then there exists a MST of $G$ that does not contain $e$. – Steven Nov 23 '19 at 16:33