2
$\begingroup$

I want to create an algorithm that determines if a given weighted undirected graph has a unique MST or not. I found an answer here, but I do not understand it. It says:

You can prove whether it has a unique MST in O(E log(V)). First find a minimum spanning tree with standard techniques. Go back to your original tree, and replace all weights with pairs of numbers, the original weight, and then 0 or 1 based on whether or not it is in the MST you found. These pairs of numbers can be added together pairwise, and compared pairwise as well - just like normal numbers. Now use the standard techniques to find a minimum spanning tree with these funny weights. The MST that you find will be the MST which shares the least edges with your original tree. Thus if there are multiple MSTs, you are guaranteed to find a different one.

Can someone explain this more thoroughly? I don't really understand what we're supposed to be doing after we find out original tree. From what I understand, once we find our original tree, we add $1$ to all the weights that are in the tree and the graph, and 0 if it is not. We then run the MST-finding algorithm again, and if we find a different tree, then we have our answer.

Why does this work?

Thank you.

$\endgroup$
2
$\begingroup$

Suppose that you have a weighted graph $G$ on $n$ vertices with integer weights, and let $W_{MST}(G)$ be the weight of the minimum spanning tree of $G$. This is the same algorithm only using plain-number mapping for simplicity (at the cost of having integer weights, but you can fix that too if you really want). The general intuition is to create an MST, and then discourage the algorithm from using these particular edges by adding a small $\varepsilon$ weight that would change the weight by a negligible amount (at most $(n-1)\cdot \varepsilon$, that is, the number of edges in a tree times $\varepsilon$).

  1. Let $k$ be the any power of $10$ strictly bigger than $n$, for example, $k = 10^{1+\lfloor\log_{10}n\rfloor}$.
  2. Construct graph $G'$ by multiplying all the weights by $k$.
  3. Calculate one particular tree $T = \operatorname{MST}(G')$.
  4. Observe that the weight of $W(T) = k \cdot W_{MST}(G)$.
  5. Form graph $G''$ from $G'$ by adding $1$ to the weight of every edge of $T$.
  6. Observe that $W_{MST}(G') \leq W_{MST}(G'') < W_{MST}(G') + n$, because the tree has at most $n-1$ edges, and to each we added at most $1$.
  7. In particular, due to $n-1 < k$, we have that $$\left\lfloor \frac{W_{MST}(G'')}{k} \right\rfloor = \frac{W_{MST}(G'')}{k} = W_{MST}(G).$$
  8. Observe that any MST of both $G'$ and $G''$ map directly to MSTs of $G$.
  9. Observe that if the MST in $G''$ and MST in $G'$ use the same edges (in particular they map to the same MST in $G$), then $$W_{MST}(G'') = W_{MST}(G') + n-1.$$
  10. As using an edge outside of $T$ is cheaper in $G''$, the above equality is satisfied if and only if there is only one MST in $G$.
  11. In other words, $W_{MST}(G'') \neq W_{MST}(G') + n-1$ implies that you have at least two MSTs in $G$ (one is $T$, and the other one is the MST from $G''$).

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ Couple of questions. You say, "The general intuition is to create an MST, and then discourage the algorithm from using these particular edges by adding a small ε weight that would not change anything but the shape of the tree." How does adding a weight to the tree change the shape of it? Was I right in my initial understanding of the algorithm? Damn I dont know, explain it to me like im five? I'm not too math heavy, which I understand is important for proofs, but is it possible to "prove" it using just words? Haha $\endgroup$ – user3026388 Mar 29 '18 at 17:45
  • 2
    $\begingroup$ @user3026388 Take a graph that is a square (a cycle on 4 vertices $a, b, c, d$) with all the edges of weight one, and run this algorithm, by hand, on this graph. Suppose the order of edges considered in point $3$ is $\{a, b\}, \{b, c\}, \{c, d\}, \{d, a\}$. Now, what made the MST of $G''$ different from $T$? What was the order in which the edges were considered? $\endgroup$ – dtldarek Mar 29 '18 at 20:25

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.