7
$\begingroup$

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
Now we decrease the weight by $k$ of an edge $e$ which does not belong to $T$.

How to efficiently update $T$ to make it an MST (denoted $T'$) of $G'=(V,E,w')$, where $w'$ is the same as $w$ except that $w'(e) = w(e) - k$?

The algorithm for updating $T$ to $T'$ is easy: Adding $e$ to $T$ creates a cycle $C$ in $T$. Let $e'$ be a maximum-weighted edge in the cycle $C$. If $w(e') > w’(e)$, then $T' = T \cup \{e\} - \{e'\}$ is the MST as desired. Otherwise, $T' = T$.

I have difficulty in proving its correctness by contradiction. Suppose $T''$ is a spanning tree of $G'$ and $w'(T'') < w'(T')$.

  • $e \notin T''$: we have $w(T'') = w'(T'') < w'(T') \le w(T)$. Contradicts with the fact that $T$ is an MST of $G$.
  • $e \in T''$: I am stuck here.

Two Notes:

  • The accepted answer here to the same question is too general for me to follow.

  • I prefer to proofs which do not rely on any concrete MST algorithms, such as Kruskal's and Prim's algorithms. However, you don't need to prove it by contradiction or separate the two cases $e \notin T''$ and $e \in T''$ as I did.

$\endgroup$
  • $\begingroup$ If the weights are integral, you might as well recompute the MST. Are you looking for an algorithm or a structural result? $\endgroup$ – Pål GD Jun 7 '15 at 17:30
  • $\begingroup$ @PålGD Recomputing an MST costs "too much" for this problem. The algorithm described in the post is linear. Actually I am looking for a formal, rigorous correctness proof for it. $\endgroup$ – hengxin Jun 8 '15 at 1:38
  • $\begingroup$ Hint: How to find the minimum spanning tree that does/doesn't contain a particular edge? $\endgroup$ – ablmf Jun 27 '16 at 19:42
  • $\begingroup$ @ablmf Thanks. Do you mean an algorithm? However, I am looking for a proof. Would you mind posting an answer if you have one? $\endgroup$ – hengxin Jun 28 '16 at 2:00
  • $\begingroup$ @hengxin The algorithm to find the minimum tree containing an edge $e$ is straightforward. Find a MST $T$. Adding $e$ to it creates a cycle. Then remove the heaviest edge other than $e$ in this cycle. If you can prove this is algorithm is correct then you're done. $\endgroup$ – ablmf Jun 28 '16 at 17:42
2
$\begingroup$

Let $T$ be a minimum spanning tree of $G$. Let $e$ be the edge we modify to get $G'$, and let $T'$ be the tree computed according to the algorithm. We know that weight of $T'$ is less than or equal to the weight of $T$.

Firstly, $T'$ is a tree - we create exactly one cycle in the algorithm, and break it, so we have no cycles in $T'$.

Secondly $T'$ is a spanning tree of $G'$. Let $e'$ be the edge removed and $e''$ be the edge added in the algorithm (we have either $e'' = e'$ or $e'' = e$) . To be a spanning tree, we must have a path between every pair of vertices $u$, $v$ using only edges of $T'$. Suppose that in $T$ (which is definitely a spanning tree), the path from $u$ to $v$ did not involve $e'$, then the same path exists in $T'$. Alternatively, suppose that it did use $e'$, then there is a path (without loss of generality) from $u$ to one endpoint of $e'$ and from the other endpoint of $e'$ to $v$. There is also a path from one endpoint of $e'$ to the other endpoint via $e''$ (around the cycle), all within $T'$. Then we can construct a path from $u$ to $v$ via $e''$ in $T'$ by merging these three paths and removing the overlap (although a walk is sufficient for connectivity).

Now, the important part, we wish to prove that $T'$ is a minimum spanning tree for $G'$.

Case 1: The algorithm does not add $e$ to the tree. In this case $T' = T$. Suppose that there is a minimum spanning tree $H$ for $G'$ that is different to $T'$. If $H$ has the same weight as $T'$, we're done. Now suppose for contradiction that the weight of $H$ is less than the weight of $T'$. There must be some edge $e'$ of lowest weight that is in $H$ but not in $T'$ (there must be some edge that does better, otherwise $G$ would not be of lower weight than $T'$, moreover we can assume that the edge that does better is the lowest weight edge that's not in $T'$ - we can take any $H'$ that is a lower weight tree than $T'$ and look at the candidate for $e'$, if it is not smaller than any edge in its cycle, then either $H'$ is not an MST, or we can create a new $H'$ where we swap the $e'$ for some edge of $T'$, this process must terminate with an edge $e'$ which has the property that it is the edge that does better).

  1. If $e' \neq e$, then consider the tree obtained by adding $e'$ to $T$ (note, not $T'$), and removing the highest weight edge on the cycle formed. This new tree has weight less than that of $T$ and is a spanning tree for $G$, contradicting the fact that $T$ is an MST for $G$ - so we know this can't happen.
  2. If $e' = e$, consider the cycle formed by adding $e' = e$ to $T'$ (i.e. the one the algorithm considered). All other edges in the cycle have lower weight than $e'$ (otherwise the algorithm would've included $e$ as an edge), and hence must be in $H$ (as $e'$ is the lowest weight edge that is not already in $T'$), but then $H$ must contain a cycle, so isn't a tree and we have a contradiction.

Case 2: The algorithm adds $e$ to $T'$. Let $x$ be the edge in $T$ that is removed by the algorithm (and hence not in $T'$) Again assume we have another MST $H$ as before. If the weight is the same, we're happy. So assume for contradiction that $H$ has lower weight, and as before $e'$ is the lowest weight edge in $H$ that's not in $T'$. We can make similar arguments as before with $x$.

  1. If $e' \neq x$, (note also that $e' \neq e$), then we can improve $T$ as before, but we know that $T$ is an MST, and recalling the property that we can assume $e'$ has lower weight that at least one edge in the cycle its addition induces, this gives a contradiction and $H$ can't exist.
  2. If $e' = x$, then again $e'$ must have higher weight than all the other edges in the cycle, hence $H$ must contain all these edges and $H$ is not a tree, and we derive a contradiction.

So in every case we derive a contradiction, therefore there can be no spanning tree of lower weight that $T'$, hence $T'$ is a minimum spanning tree for $G'$.

$\endgroup$
  • $\begingroup$ Thanks for your efforts. Some confusion about the statement "If $e' \neq x$ (note also that $e' \neq e$), then we can ..." in Case 2.1: (1) why is $e' \neq e$? Do you assume that $e \in H$? (2) To improve $T$ by adding $e'$ to it and removing another edge, say $e''$, we must show that $e' \notin T$ and $w(e'') > w(e')$. How do you guarantee these? $\endgroup$ – hengxin Jun 8 '15 at 3:32
  • $\begingroup$ @hengxin because in 2.1 $e'$ is not in $T'$, but $e$ is, so they can't be the same. $\endgroup$ – Luke Mathieson Jun 8 '15 at 6:44
  • $\begingroup$ OK, I see. Then what about my second question? I think I have proved that $e' \notin T$, so we can add $e'$ to $T$ to create a cycle. However, how do you guarantee that there is an edge, say $e''$, in the cycle of greater weight than $w(e')$ so that we can improve $T$ by removing $e''$? $\endgroup$ – hengxin Jun 8 '15 at 8:40
  • $\begingroup$ @hengxin, sorry missed the (2) in there $e' \neq x \neq e$, and $x$ and $e$ is the only swap from $T$ to $T'$, so $e'$ must be a different, third edge that's in nether $T$ nor $T'$, and the properties we had before are true again, if $H$ were a better MST, then $e'$ must weigh less than some edge in $T$, in particular, it must weigh less than some edge in the cycle it creates (otherwise all those edges must also be in $H$, and $H$ isn't a tree). $\endgroup$ – Luke Mathieson Jun 8 '15 at 9:45
  • $\begingroup$ Still confused. I am almost lost in the "forest" of trees. I know $e'$ weighs less than some edge in $T'$: why does it also weigh less than some edge in $T$? Suppose it does, why does it weigh less than some edge in the cycle (I don't understand the "otherwise")? Can other edges all have equal weights with $w(e')$? Do you have the time for a chat? $\endgroup$ – hengxin Jun 8 '15 at 11:14
1
$\begingroup$

Let me introduce a useful theorem about minimum spanning tree (MST) before we can understand the simple proof below.

Theorem: A local minimum Spanning Tree is an MST

Let G be a (simple finite) undirected connected edge-weighted graph $G$. Let $S$ be a spanning tree of $G$. Then $S$ is an MST if and only if for any edge $e$ not in $S$, $e$ is a heaviest edge in the (simple) cycle created when we add $e$ to $S$.

The theorem shows that we can verify an MST edge by edge although MST is defined with respect to all edges in the same time.

A proof of the theorem by the OP herself/himself does not rely on any MST algorithm, which makes this answer fit OP's preference for no reliance on any MST algorithm. It is a minor mystery that OP missed the simple proof below.

In another proof of the theorem stated differently you can also find the meaning of a spanning tree being "a local minimum", although it is not needed to understand that in order to understand this answer.

Armed with the above theorem, the readers are encouraged to construct a proof by themselves, which is probably easier than reading my rigorous proof below.

A simple proof of the algorithm in OP's question

Let us reuse all notations in OP's definition of the algorithm. To prove $T'$ is an MST of $G'$, there are two cases.

  • when $w(e')\leq w'(e)$ and $T'=T$.

    Since the only difference between T in G and T' in G' is the weight of edge $e$, we need to check $e$ only. Since $e'$ is a heaviest edge in $C$ with $w$, the condition $w'(e) \geq w(e')$ means that $e$ is a heaviest edge in $C$ with $w'$. We are done in this case.

  • when $w(e')\gt w'(e)$ and $T' = T \cup \{e\} - \{e'\}$.

    1. Let us consider $e'$. The cycle created when we add $e'$ to $T'$ is also $C$. Since $e'$ is a heaviest edge in $C$ with $w$, the new weight of $e$, $w'(e) \lt w(e')$ means that $e'$ remains a heaviest edge in $C$ with $w'$.
    2. Now let $f\neq e'$ be an edge not in $T'$. Let $D$ be the cycle created when we add $f$ to $T$. Since $T$ is an MST of $G$, $\,f$ is a heaviest edge in $D$ with $w$.
      • If $e'\notin D$, $D$ is also the cycle created when we add $f$ to $T'$. As $w$ and $w'$ are the same on $D$, $\,f$ remains a heaviest edge in $D$ with $w'$.
      • Now suppose $e'\in D$. If we replace $e'$ with all edges in $C$ other than $e'$, we get from $D$ a new cycle $D'$, which is the cycle created when we add $f$ to $T'$. Since $e'$ is a heaviest edge in $C$ with $w$, $f$ remains a heaviest edge in $D'$ with $w$. Since the only difference between $w$ and $w'$ is their values on $e$, for which we have $w'(e) \lt w(e') \leq w(f) = w'(f)$, we see that $f$ remains a heaviest edge in $D'$ with $w'$.
    3. Combining step 1 and 2, we are done in this case.

We note that both the algorithm and the proof above works actually for all cases when the weight of $e$ is changed, regardless of whether it is decreased or intact or increased.

Why do I consider my answer is better than other answers?

One might argue that my answer is more complex since it uses an extra theorem. Well, other answers have (probably) embedded an implicit long proof of that theorem. That implicit long proof are interwoven with other parts of those answers, making them a dense forest of ideas that are hard to understand as seen in the comments to those answers. It is a situation similar to a huge method/procedure/function in a program that accomplishes a big task without taking advantage of standalone reusable helper methods. It also happens that the helper theorem presented above is clear, simple and reusable.)

A minor note on the equal weights

It is a common practice to assume distinct weights of all edges for the sake of easier writing. However, this post deals with possibly equal weights throughout. Note that we have only been referring to "a heaviest edge" but never "the heaviest edge".

$\endgroup$

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.