  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. al. 2023.
