# Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 13 Dec 2024.

## Builds on (most cited first, 10 of 10)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Private Graph Data Release: A Survey](https://mlsanity.com/paper/2107.04245/) (2021)
- [Shortest Paths and Distances with Differential Privacy](https://mlsanity.com/paper/1511.04631/) (2015)
- [Minimum spanning tree release under differential privacy constraints](https://mlsanity.com/paper/1801.06423/) (2018)
- [Graph-based Clustering under Differential Privacy](https://mlsanity.com/paper/1803.03831/) (2018)

## Abstract (arXiv)

We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph G = (V, E, vecW) where V is a set of n vertices, E is a set of m undirected edges, and  vecW ∈ ℝ|E|  is an edge-weight vector, our goal is to publish an approximate MST under edge-weight differential privacy, as introduced by Sealfon in PODS 2016, where V and E are considered public and the weight vector is private. Our neighboring relation is ℓ_∞-distance on weights: for a sensitivity parameter Delta_∞, graphs  G = (V, E, vecW)  and  G' = (V, E, vecW')  are neighboring if |vecW-vecW'|_∞ ≤ Delta_∞. Existing private MST algorithms face a trade-off, sacrificing either computational efficiency or accuracy. We show that it is possible to get the best of both worlds: With a suitable random perturbation of the input that does not suffice to make the weight vector private, the result of any non-private MST algorithm will be private and achieves a state-of-the-art error guarantee. Furthermore, by establishing a connection to Private Top-k Selection [Steinke and Ullman, FOCS '17], we give the first privacy-utility trade-off lower bound for MST under approximate differential privacy, demonstrating that the error magnitude, tildeO(n3/2), is optimal up to logarithmic factors. That is, our approach matches the time complexity of any non-private MST algorithm and at the same time achieves optimal error. We complement our theoretical treatment with experiments that confirm the practicality of our approach.