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.

  • $\begingroup$ 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 ? $\endgroup$
    – Optidad
    Nov 22 '19 at 16:15

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.

  • $\begingroup$ what is the cycle rule? that the part i couldn't get in my proof. $\endgroup$
    – Amir Mor
    Nov 23 '19 at 15:32
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Nov 23 '19 at 16:33

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.