# Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2022.

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

- [Differentially Private Data Release on Graphs: Inefficiencies and Unfairness](https://mlsanity.com/paper/2408.05246/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)

## Abstract (arXiv)

We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ1-distance. We give an ε-DP algorithm with additive error tildeO(n2/3 / ε) and an (ε, δ)-DP algorithm with additive error tildeO(√n / ε) where n denotes the number of vertices. This positively answers a question of Sealfon (PODS'16), who asked whether a o(n)-error algorithm exists. We also show that an additive error of Omega(n1/6) is necessary for any sufficiently small ε, δ > 0. Finally, we consider a relaxed setting where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, %2k - 1, the additive error can be reduced to tildeOleft(n1/2 + O(1/k) / εright) in the ε-DP case and tildeO(n1/3 + O(1/k) / ε) in the (ε, δ)-DP case, respectively.