Minimum spanning tree algorithms that use only rankings achieve low distortion
On the Metric Distortion of the Minimum Spanning Tree Problem
Data Structures and Algorithms
Summary
This paper looks at how well minimum spanning trees (MSTs) can be found when you only know the order of distances between points, not the exact distances. The authors show it’s impossible to get a perfect MST from just rankings in general, but they design algorithms that get reasonably close. For special kinds of spaces, like tree-shaped or doubling metrics, their methods recover MSTs with very small errors using only order information. They also look at how asking a few clever comparisons helps make the approximation even better.
What this means in practice
- •For network engineers: Design communication networks using only relative link quality rankings instead of exact measurements to build efficient spanning trees with bounded distortion.
- •For distributed system developers: Implement MST constructions when nodes only provide rank-order preferences on connections, enabling near-optimal tree structures with limited numeric information.
Authors
Kian Ghassemi, Masoud Seddighin, Saeed Seddighin
Abstract
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices induced by these weights. We first show, through a simple example, that without assumptions on the weights, no ordinal algorithm guarantees a finite approximation ratio. We therefore focus on general metrics and present a Borůvka-inspired algorithm using only ordinal comparisons that achieves distortion $O(\log n)$. We complement this result by showing that, for every $\varepsilon>0$, no deterministic ordinal algorithm guarantees distortion at most $3/2-\varepsilon$ on all finite metric instances. We then investigate more informative settings in pursuit of constant distortion, first considering two well-studied metric classes. For tree metrics realized on the given vertex set, a more careful variant of our initial algorithm achieves distortion~$1$, recovering an optimal MST from ordinal information alone. For the broad class of doubling metrics, a different algorithm based on \emph{endpoint cut stability} achieves distortion $2^{O(D)}$, where $D$ is the doubling dimension; this is constant for fixed $D$, independently of $n$. Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with $n\geq2$, fewer than $n$ edge-comparison queries suffice to achieve distortion at most $2\log_2^* n-1$, which is near-constant even for very large inputs.