# Near-Universally-Optimal Differentially Private Minimum Spanning Trees

arXiv: https://arxiv.org/abs/2404.15035 · HTML: https://mlsanity.com/paper/2404.15035/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2024.

## Built on by (most cited first, 2 of 2)

- [Faster Private Minimum Spanning Trees](https://mlsanity.com/paper/2408.06997/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)

## Abstract (arXiv)

Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the ℓ1 neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the ℓ_∞ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the ℓ1 and the ℓ_∞ neighbor relations.