Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given a weighted, undirected graph with n vertices, a minimum s-t cut is a bipartition of the vertices which separates vertices s and t while minimizing the sum of edge weights crossing the partition. A celebrated result of Gomory and Hu from the 60s shows that there exists a tree on the same vertices as the graph with the same minimum s-t cuts as the original graph for all distinct s and t. The result is algorithmic, and a recent line of work has improved the efficiency of algorithms to compute a Gomory-Hu tree, culminating in a near-linear time algorithm by Abboud, Li, Panigrahi and Saranurak.

We develop an algorithm for computing a Gomory-Hu tree of a graph without leaking information about individual edge weights via differential privacy. Differential privacy (DP) is a formalization for individual privacy which has received significant attention when dealing with sensitive data about people. We design an approximate Gomory-Hu tree algorithm which preserves ε-DP with additive error O(n polylog(n)/ε). Additive error Ω(n) is necessary even for privately estimating a single minimum s-t cut (Dalirrooyfard, Mitrović, Nevmyvaka), and prior state-of-the-art DP algorithms for Gomory-Hu trees required O(n^(1.5)/ε) error. Our work shows that all O(n^2) minimum s-t cuts can be simultaneously approximated as accurately (up to logarithmic factors) as a single minimum s-t cut. To achieve this result on private algorithms, we surprisingly rely on recent tools developed for fast Gomory-Hu algorithms including a DP version of the minimum isolating cuts procedure.

This is joint work with Anders Aamand, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu.