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

Preprint · Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson

- Archive id: arxiv:2203.16476
- Published: 2022-03-30
- arXiv: https://arxiv.org/abs/2203.16476
- Source URL: https://arxiv.org/abs/2203.16476
- PDF: https://arxiv.org/pdf/2203.16476
- Provenance: arxiv

## Abstract

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 $\\ell\_1$-distance. We give an $ε$-DP algorithm with additive error $\\tilde{O}(n^{2/3} / ε)$ and an $(ε, δ)$-DP algorithm with additive error $\\tilde{O}(\\sqrt{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 $Ω(n^{1/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 $\\tilde{O}\\left(n^{1/2 + O(1/k)} / ε\\right)$ in the $ε$-DP case and $\\tilde{O}(n^{1/3 + O(1/k)} / ε)$ in the $(ε, δ)$-DP case, respectively.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.