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?

  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user5810
    Mar 26 '14 at 14:09
  • $\begingroup$ @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. $\endgroup$ Mar 26 '14 at 16:15
  • $\begingroup$ @RickyDemer: Indeed. Fixed. $\endgroup$
    – Adi Shavit
    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.

On the other hand, I can imagine a heuristic that accumulates lower bounds and often argues itself out of computing weights of some edges in practical problems. It just can't guarantee to perform better than standard algorithms in the worst case.


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.