0
$\begingroup$

In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor:

Let  $T$  be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best Minimum Spanning Tree differs from  $T$  by one edge replacement. (For a proof of this statement refer to CLRS (3rd ed.) problem 23-1 here).

So we need to find an edge  $e_{new}$  which is in not in  $T$ , and replace it with an edge in  $T$  (let it be  $e_{old}$ ) such that the new graph  $T' = (T \cup \{e_{new}\}) \setminus \{e_{old}\}$  is a spanning tree and the weight difference ( $e_{new} - e_{old}$ ) is minimum.

It is questionable that the algorithms hinge on the lemma that the second best Minimum Spanning Tree differs from the Minimum Spanning Tree by one edge replacement. The word the in a Minimum Spanning Tree context is commonly understood to imply that it is unique but the algorithms supposedly work for all graphs.

In the problem 23-1 Second-best minimum spanning tree and the proof being cited above:

Let $G = (V, E)$ be an undirected, connected graph whose weight function is $w : E \rightarrow \mathbb{R}$, and suppose that $\lvert E\rvert \geq \lvert V\rvert$ and all edge weights are distinct.

Let $T$ be the minimum spanning tree of $G$. Prove that $G$ contains some edge $(u, v) \in T$ and some edge $(x, y) \notin T$ such that $T - \{(u, v)\} \cup \{(x, y)\} $ is a second-best minimum spanning tree of $G$.

Proof (sketch). Let $T$ be an MST and $T'$ be a second-best MST. Suppose for contradiction, there are two edges in $T - T'$, and let $e$ be an edge in $T - T'$ with minimum weight. If we add $e$ to $T'$, we get a cycle $c$, which contains an edge $e'$ in $T' - T$.

We claim that $w(e') > w(e)$. We prove this by contradiction, assume $w(e') < w(e)$. If we add $e'$ to $T$, we get a cycle $c'$, which contains an edge $e''$ in $T - T'$. Therefore, $T'' = T - e'' + e'$ forms an ST, and we must also have $w(e'') < w(e')$, since otherwise $w(T'') < w(T)$. Thus, $w(e'') < w(e') < w(e)$ contradicts $e$ being an edge with minimum weight in $T - T'$.

Since $e$ and $e'$ would be on a common cycle if we add $e$ to $T'$, $T'' = T' - e' + e$ forms an ST which differs from $T$ by only one edge, and we have $w(T'') < w(T')$. Hence, $T''$ is a second-best MST.

The skepticism is warranted as it turns out that both the problem and the proof rests on the assumption of distinct edge weights which is a sufficient condition for the uniqueness of Minimum Spanning Tree.

There is an added problem that every other proof on the internet is all related to this CLRS (3rd ed.) problem 23-1 that assumes distinct edge weights, and the topic of second best Minimum Spanning Tree has never even been asked on this site.

Is it possible to prove this without distinct edge weights assumption? Is there another proof without distinct edge weights assumption? Is it possible to modify the above proof to work without distinct edge weights assumption?

It should be noted that it is only possible to extend the proof by defining a second best minimum spanning tree as a spanning tree different from a given minimum spanning tree with the least weight. It is used in an onlinejudge practical problem of finding two cheapest MST to choose from.

$\endgroup$
5
  • $\begingroup$ Please define what is a "second best Minimum Spanning Tree" (especially when the minimum spanning tree of G is not unique). There can be two different definitions. Definition one: given a minimum spanning tree, a second best minimum spanning tree is another (meaning different) spanning tree with the least weight as possible. That is, a second best minimum spanning tree can be a minimum spanning tree as well. Definition two: a second best minimum spanning tree is a spanning tree with the least weight that is greater than the weight of a minimum spanning tree. $\endgroup$
    – John L.
    Commented Mar 18 at 1:13
  • $\begingroup$ It looks whichever definition you choose, your proof could be considered insufficient. By the way, it is nice to see your self-question and answer. $\endgroup$
    – John L.
    Commented Mar 18 at 1:17
  • $\begingroup$ @JohnL. Thank you for the response. I use the first definition as it is the only definition that extends the original definition while maintaining the validity of the argument, and it is applied this online judge problem on electric grid redundancy. It appears the proof is sufficient as I just discovered this proof from flashmt's comment in codeforces, what do you think? $\endgroup$ Commented Mar 19 at 15:39
  • $\begingroup$ Instead of "updating an edge", it is better to write "replacing an edge". $\endgroup$
    – John L.
    Commented Mar 19 at 23:10
  • $\begingroup$ @JohnL. I agree, it is consistent with the definition used in the source. I have edited the question and added another answer. $\endgroup$ Commented Mar 21 at 14:34

2 Answers 2

0
$\begingroup$

The proof provided may be modified to work without distinct edge weights assumption:

Proof (sketch). Let $T$ be an MST and $T'$ be a second-best MST. Suppose for contradiction, there are two edges in $T - T'$, and let $e$ be an edge in $T - T'$ with minimum weight. If we add $e$ to $T'$, we get a cycle $c$, which contains an edge $e'$ in $T' - T$.

We claim that $w(e') ≥ w(e)$. We prove this by contradiction, assume $w(e') < w(e)$. If we add $e'$ to $T$, we get a cycle $c'$, which contains an edge $e''$ in $T - T'$. Therefore, $T'' = T - e'' + e'$ forms an ST, and we must also have $w(e'') ≤ w(e')$, since otherwise $w(T'') < w(T)$. Thus, $w(e'') ≤ w(e') < w(e)$ contradicts $e$ being an edge with minimum weight in $T - T'$.

Since $e$ and $e'$ would be on a common cycle if we add $e$ to $T'$, $T'' = T' - e' + e$ forms an ST which differs from $T$ by only one edge, and we have $w(T'') ≤ w(T')$. Hence, $T''$ is a second-best MST.

Therefore, second-best MST algorithms are optimal without distinct edge weights assumption.

$\endgroup$
0
0
$\begingroup$

There is a proof on the internet without distinct edge weights assumption found in this document from flashmt's comment in codeforces. It is the equivalent of the proof provided, only written more tersely:

Given connected graph $G = (V, E)$ where $\lvert E \rvert \geq \lvert V \rvert$. There exists an edge $(x, y) \in$ MST and an edge $(u, v) \notin$ MST such that we can obtain second-best MST by replacing $(x, y)$ with $(u, v)$ in MST.

Proof: Let $T$ be an MST and $T'$ be a second-best MST. Let $(x, y)$ be an arbitrary edge $\in T - T'$. Hence, $T' + (x, y)$ contains a cycle and one edge in this cycle is not in $T$. Let this edge be $(u, v)$. We have $w(x, y) \leq w(u, v)$ (otherwise $T - (x, y) + (u, v)$ would be a better MST than $T$).

  • If $w(x, y) = w(u, v)$, $T - (x, y) + (u, v)$ will be the second-best MST with same cost as MST.

  • If $w(x, y) < w(u, v)$, let $T'' = T' - (u, v) + (x, y)$, hence $T'' < T'$, thus $T'' = T$ since only MST $<$ second-best MST, ergo $T - (x, y) + (u, v)$ will be the second-best MST.

In addition to the Kruskal and Lower Common Ancestor approaches provided, the document provides the Disjoint Set approach yielding equivalent time complexity between second-best MST and MST.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.