Differentially Private Gomory-Hu Trees

Given an undirected, weighted $n$-vertex graph $G=(V,E,w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ that preserves the Min-$s$-$t$-Cut between any pair of vertices $s,t\in V$. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection.

We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\epsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\epsilon )$-additive approximations of the Min-$s$-$t$-Cuts in $G$ for all distinct $s,t\in V$ with high probability.

Our error bound is essentially optimal, since Dalirrooyfard, Mitrovic and Nevmyvaka, Neurips 2023 showed that privately outputting a single Min-$s$-$t$-Cut requires $\Omega (n)$ additive error even with $(\epsilon ,\delta )$-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\epsilon )$ for $\epsilon$-DP Gupta, Roth, Ullman, TCC 2009 and $\tilde{O}(\sqrt{mn}/\epsilon )$ for $(\epsilon ,\delta )$-DP Liu, Upadhyay and Zou, SODA 2024, both achieved by DP algorithms that preserve all cuts in the graph.

To achieve our result, we develop an $\epsilon$-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle "bounded overlap" computational branches in recursive algorithms, which maybe of independent interest.