2025/04/04 by Michael Dinitz, Dinitz, Michael, Chenglin Fan +7
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2504.03354
openalex publication_date 2025/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as recursively separable. In particular, for any n-vertex Kh-minor-free graph, our algorithm achieve an additive error of \widetildeO(h(nW)1/3 ) , where W represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of \widetildeO(n1/4√(W)). Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are recursively separable.