# Minimum Spanning Tree of Graph with Unknown Weights

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we have $w(v,y) \leq w(v,u)+w(u,y)$.
However, it is expensive to calculate $w(\cdot)$.

My question is, is there an algorithm that can calculate the minimum spanning tree, without calculating all $n(n-1)/2$ edge weights?

• Is the graph directed? $\:$ If no, then there are only $(n\cdot (n\hspace{-0.04 in}-\hspace{-0.05 in}1))/2$ edge weights. $\;\;\;\;$
– user5810
Mar 26 '14 at 14:09
• @Ricky Demer $w$ seems to be a metric and a metric is symmetric, so there should indeed only be $n \cdot (n-1) / 2$ edge weights. Mar 26 '14 at 16:15
• @RickyDemer: Indeed. Fixed. Mar 26 '14 at 18:11

In general the triangle inequality will not help. To see this, recall that the minimum spanning tree depends only on the relative order of the weights. Take an arbitrary MST problem and scale all the weights to lie in $[2,3]$. Now the triangle inequality is satisfied but the MST is the same.
To put it another way, if in your problem the edge weights all happen to lie in $[2,3]$, you must find the weight of every edge since the one you didn't find the weight of can still be the smallest no matter what the weights of all the other edges are.