Differentially Private Gomory-Hu Trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917740739035136 |
|---|---|
| author | Aamand, Anders Chen, Justin Y. Dalirrooyfard, Mina Mitrović, Slobodan Nevmyvaka, Yuriy Silwal, Sandeep Xu, Yinzhan |
| author_facet | Aamand, Anders Chen, Justin Y. Dalirrooyfard, Mina Mitrović, Slobodan Nevmyvaka, Yuriy Silwal, Sandeep Xu, Yinzhan |
| contents | Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-Hu tree is a well-studied problem in graph algorithms and has received considerable attention. In particular, a long line of work recently culminated in constructing a Gomory-Hu tree in almost linear time [Abboud, Li, Panigrahi and Saranurak, FOCS 2023].
We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-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, as [Dalirrooyfard, Mitrović and Nevmyvaka, NeurIPS 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $Ω(n)$ additive error even with $(1, 0.1)$-DP and allowing for a multiplicative error term. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] and $O(\sqrt{mn} \cdot \text{polylog}(n/δ) / \varepsilon)$ for $(\varepsilon, δ)$-DP [Liu, Upadhyay and Zou, SODA 2024], both of which are implied by differential private algorithms that preserve all cuts in the graph. An important technical ingredient of our main result is an $\varepsilon$-DP algorithm for computing minimum Isolating Cuts with $\tilde{O}(n / \varepsilon)$ additive error, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01798 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differentially Private Gomory-Hu Trees Aamand, Anders Chen, Justin Y. Dalirrooyfard, Mina Mitrović, Slobodan Nevmyvaka, Yuriy Silwal, Sandeep Xu, Yinzhan Data Structures and Algorithms Cryptography and Security Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-Hu tree is a well-studied problem in graph algorithms and has received considerable attention. In particular, a long line of work recently culminated in constructing a Gomory-Hu tree in almost linear time [Abboud, Li, Panigrahi and Saranurak, FOCS 2023]. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is $\varepsilon$-DP, runs in polynomial time, and can be used to compute $s$-$t$ cuts that are $\tilde{O}(n/\varepsilon)$-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, as [Dalirrooyfard, Mitrović and Nevmyvaka, NeurIPS 2023] showed that privately outputting a single Min-$s$-$t$-Cut requires $Ω(n)$ additive error even with $(1, 0.1)$-DP and allowing for a multiplicative error term. Prior to our work, the best additive error bounds for approximate all-pairs Min-$s$-$t$-Cuts were $O(n^{3/2}/\varepsilon)$ for $\varepsilon$-DP [Gupta, Roth and Ullman, TCC 2012] and $O(\sqrt{mn} \cdot \text{polylog}(n/δ) / \varepsilon)$ for $(\varepsilon, δ)$-DP [Liu, Upadhyay and Zou, SODA 2024], both of which are implied by differential private algorithms that preserve all cuts in the graph. An important technical ingredient of our main result is an $\varepsilon$-DP algorithm for computing minimum Isolating Cuts with $\tilde{O}(n / \varepsilon)$ additive error, which may be of independent interest. |
| title | Differentially Private Gomory-Hu Trees |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2408.01798 |