8
$\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'$.

| cite | improve this answer | |
$\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
  • 1
    $\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
2
$\begingroup$

Let $S$ be a spanning tree of an edge-weighted graph $G$. We call $S$ a local-minimum spanning tree of $G$ if for any edge $e$ not in $S$, $e$ is a heaviest edge in the cycle created when we add $e$ to $S$.

Let me introduce a theorem about minimum spanning tree (MST).

A spanning tree is an MST if and only if it is a local-minimum spanning tree.

A proof of the above theorem by the OP herself/himself does not rely on any concrete MST algorithm.

In another proof of the above theorem but stated differently, you can also read the reason why such a spanning tree is called "local-minimum".

The above theorem enables us to verify an MST edge by edge although MST is defined with respect to all edges together.


Once we are armed with the above theorem, it becomes easy to prove the correctness of the algorithm in the question. It should be, in fact, easier to construct a proof by yourself than reading the rigorous proof below.

A simple proof of the algorithm in the question

Let us reuse all notations in OP's definition of the algorithm.

Note that $T$ is a local-minimum spanning tree of $G$. To prove $T'$ is an MST of $G'$, we will show $T'$ is a local-minimum spanning tree 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.

Note that both the algorithm and the proof above work well regardless whether the weight of $e$ is decreased, intact or increased.

On the equal weights of edges

It is a common practice to assume distinct weights of all edges for the sake of clearer exposition. However, this post works well with possibly equal edge-weights. In particular, we have been referring to "a heaviest edge" but never "the heaviest edge".

| cite | improve this answer | |
$\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.