pipette
ESEspañol

On the Metric Distortion of the Minimum Spanning Tree Problem

Kian Ghassemi, Masoud Seddighin, Saeed Seddighin

Preprint

In the authors' words

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\r{u}vka-inspired algorithm using only ordinal comparisons that achieves distortion . We complement this result by showing that, for every , no deterministic ordinal algorithm guarantees distortion at most 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~, recovering an optimal MST from ordinal information alone. For the broad class of doubling metrics, a different algorithm based on endpoint cut stability achieves distortion , where is the doubling dimension; this is constant for fixed , independently of . Finally, we study a query-based extension allowing comparisons between two edge lengths without revealing their numerical values. For general metrics with , fewer than edge-comparison queries suffice to achieve distortion at most , which is near-constant even for very large inputs.

Main resultLimitation the authors admit

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 24 pages, 9 figures, 1 table