  Devising mechanisms with good beyond-worst-case input-dependent performance
has been an important focus of differential privacy, with techniques such as
smooth sensitivity, propose-test-release, or inverse sensitivity mechanism
being developed to achieve this goal. This makes it very natural to use the
notion of universal optimality in differential privacy. Universal optimality is
a strong instance-specific optimality guarantee for problems on weighted
graphs, which roughly states that for any fixed underlying (unweighted) graph,
the algorithm is optimal in the worst-case sense, with respect to the possible
setting of the edge weights.
  In this paper, we give the first such result in differential privacy. Namely,
we prove that a simple differentially private mechanism for approximately
releasing the minimum spanning tree is near-optimal in the sense of universal
optimality for the $\ell_1$ neighbor relation. Previously, it was only known
that this mechanism is nearly optimal in the worst case. We then focus on the
$\ell_\infty$ neighbor relation, for which the described mechanism is not
optimal. We show that one may implement the exponential mechanism for MST in
polynomial time, and that this results in universal near-optimality for both
the $\ell_1$ and the $\ell_\infty$ neighbor relations.
