Distinct edge weight assumption in MST algorithms

Question

My lecture notes for minimum spanning trees say that:

A graph can have several minimum spanning trees but if the edge weights are distinct then the minimum spanning tree is unique. Without loss of generality, we can assume that the edge weights are distinct

I'm trying to convince myself that the distinct edge weights assumption in MST algorithms is a valid one but haven't made much progress. I thought about maybe considering the smallest absolute difference between two adjacent edge weights (call this $\delta$) and then let $\alpha = \delta / m$ where $m$ is the number of edges. If there's $k$ edges of the same weight $w$, order them arbitrarily and replace the edge weight by $w + i\times\alpha$ for 0ドル\le i<k$. Then all edge weights are unique and any MST algorithm applied for these new weights should give a valid MST for the original weights. I'm not convinced that this works though.

• user16034: What do you mean ? What could be wrong ?

Answer 1

You are on the right track. A bit more work is needed.

---

Suppose we have developed a comparison-based MST algorithm $\mathcal A$ for graphs of distinct edge-weights. (You will probably not see an MST algorithm that is not comparison-based.)

Let $G=(E,V,w)$ be a weighted graph where edge-weights might have duplicates. How can we obtain an MST of $G$ using $\mathcal A$?

We can run $\mathcal A$ on $G$, breaking ties among the same edge-weights arbitrarily and consistently, to obtain a spanning tree $T$. However, is $T$ an MST of $G$ still? That is your question.

Let we sort all edge-weights (with duplicates) according to the same tie breaking rules when we ran $\mathcal A$ to obtain $T$. Suppose we get $e_1, \cdots, e_m$. Let $\delta_E$ be the smallest nonzero absolute difference between two edge-weights. Let $\delta_G$ be the smallest nonzero absolute difference between the weights of two spanning trees of $G$. If all edge-weights are the same or all weights of spanning trees are the same, $T$ is trivially an MST. Assume otherwise, so both $\delta_E$ and $\delta_G$ are well-defined. Let $G^+=(V, E, w^+)$, where $$w^+(e_i)=w(e_i)+\frac{i\min(\delta_E, \delta_G)}{n^2}.$$ Then $$i<j\iff w^+(e_i)<w^+(e_j).$$ In particular, all edge-weights of $G^+$ are distinct.

Now we run $\mathcal A$ on $G^+$. Since the comparison order of all edges for $G$ is the same as that of $G^+$, the same spanning tree $T$ will be obtained. Since $\mathcal A$ is an MST algorithm, $w^+(T)\le w^+(T')$ for any spanning tree $T'$ of $G^+$ (or of $G$, since the spanning trees of $G$ are the same as the spanning trees of $G^+$).

$$w(T)<w^+(T)\le w^+(T')\le w(T')+(n-1)\frac{n\delta_G}{n^2}<w(T')+ \delta_G$$

By the definition of $\delta_G$, this means $w(T)<w(T')$.

• 喜欢算法和数学: Another way to convince yourself is to follow the proof of each MST algorithm, checking that it is valid for graphs with possible equal edge-weights. It does not prove for all comparison-based MST algorithms, of course.
• Kenneth Kho: would this argument hold if the algorithm is for a second-best MST instead? this problem has a convenient LCA-based solution that rests on the assumption that the second-best MST is always one edge different from the MST which in turn hinges on the assumption of distinct edge weights. since i'm unable to find answers, can you justify a bit how this could also work without distinct edge weights? cp-algorithms.com/graph/second_best_mst.html viterbi-web.usc.edu/~shanghua/teaching/Spring2010/public_html/…
• Kenneth Kho: for a second-best MST, read my self-answer at "Distinct edge weights assumption in second best MST algorithms only updating an edge in MST"

Answer 2

The real question is: if we assign arbitrary priorities to edges of equal weights, can that break an MST algorithm ? Though this can lead to different MST's, neither the tree-ness property, nor the spanning property nor the minimum weight will be invalidated.

Assigning priorities can be done

• a priori, for instance by numbering the nodes and using the lexicographocal ordering based on (weight, number);

• a posteriori, by declaring that the edges effectively chosen during the resolution had a higher priority.