Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

Rasmus Pagh, Lukas Retschmeier, Hao Wu +1

We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph $G=(V,E,\vec{W})$ where $V$ is a set of $n$ vertices, $E$ is a set of $m$…