Differentially Private All-Pairs Shortest Distances for Low Tree-Width Graphs. (arXiv:2306.05916v1 [cs.DS])

In this paper, we present a polynomial time algorithm for the problem of
differentially private all pair shortest distances over the class of low
tree-width graphs. Our result generalizes the result of Sealfon 2016 for the
case of trees to a much larger family of graphs. Furthermore, if we restrict to
the class of low tree-width graphs, the additive error of our algorithm is
significantly smaller than that of the best known algorithm for this problem,
proposed by Chen et. …

algorithm case class family graphs low private problem result trees