Determine if a given weighted graph has unique MST

Question

I'm looking for an algorithm (or any other way) to determine if a given weighted graph has unique MST (Minimum spanning tree) in O(ElogV)?

I don't know anything about the weights (e.g. weight(e1) != weight(e2)), and the algorithm just return True if this graph has only one unique MST or False if not.

I started by using Kruskal's algo, and check if find-set(u)==find-set(v) so there is a circle in the MST, but this way does not cover all the scenarios as I thought :(

Thanks a lot! Tomer.

Genuflection

Not a MST expert but I don't think you can check that it only has 1 MST in O(ElogV). Is there a reason you believe you can? – Lycian

possible duplicate of Graph Has Two / Three Different Minimal Spanning Trees ? – Landrum

@Lycian O(ElogV) is the time complexity of Kruskal algo / Prim algo for finding MST of a given graph, so the solution must be a variation of those algorithms... – Genuflection

Answer 1

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.

Sunken

What you mean in this description, "These pairs of numbers can be added together pairwise, and compared pairwise as well". Can you please give a simple example to prove uniqueness with in this logic ? – Costa

@ArunprasadRajkumar We're just considering ordered pairs of numbers. Two add two pairs you add the first of each to get the first number, and the second to get the second. Think of adding vectors. And you compare them by comparing the first and then breaking ties with the second. – Sunken