In this paper
AbstractIntroductionPreliminariesAlgorithm for DP All-Pairs Min-Cut ValuesA Lower Bound for Releasing All-Pairs Min-Cut ValuesDeclaration of AI UseProof of SVT TheoremReferencesWorksComputer Science
Differentially Private All-Pairs Min Cut Values
Abstract
We study the problem of privately releasing the min cut values of all pairs of vertices in a given -node weighted graph, under the edge-neighboring model. Straightforward application of advanced composition yields an approximate DP algorithm that outputs all min cut values up to additive error. Prior works [Dalirrooyfard, Mitrovi{ć} and Nevmyvaka, 2023; Aamand et al., 2026] have established that is the correct bound if the algorithm also needs to output cuts that realize the approximate min cut values. On the other hand, simply outputting the values could be an easier problem, but prior algorithms have been stuck on the bound. In this work, we give an approximate DP algorithm outputting all-pair min cut values with additive error, beating the linear error barrier. Our algorithm applies the sparse vector technique [Dwork and Roth, 2014] to maintain a hierarchical decomposition of the vertices based on the min cut structure. We also prove an lower bound for this problem.
Introduction
Given a weighted graph7 , a vertex partition is called a cut, and the sum of weights of the edges with one endpoint in and another endpoint in is called the value of that cut. Recently, there has been increasing interest in understanding cut problems in the context of differential privacy, including global min cut [12], min - cut [6 CDFZ26], all-pairs min - cuts [2], cut sparsifier [13, 10, 15, 1], and more [14, 6 CDFZ26]. In these works and also in our paper, the model of neighboring datasets is edge-neighboring: two neighboring graphs are those whose total edge weights differ by at most one, and in a single edge.
We consider one of the simplest problems: min - cut. This problem admits an interesting behavior depending on what exactly we wish to output. For a fixed pair , it is known how to output an entire - cut8 with an -DP algorithm, whose cut value in the underlying graph differs by from the actual min - cut [6]. The additive error bound is also known to be tight [6]. Interestingly, the same bound can be achieved even if one needs to privately output an approximate min - cut for every pair [2].
On the other hand, if the goal is instead to output the (approximate) cut values, one can potentially do much better. For example, to output a single min - cut value privately, we only need to naively add noise to the true min - cut value, resulting in additive error (in expectation), which is much smaller than the bound. However, it seems more challenging to output the values of all min - cut with lower additive error than privately releasing the cuts themselves. Namely, since there are values to output, we can apply advanced composition to achieve additive error (with approximate DP), which matches the error bound of [2], but is significantly weaker since the algorithm in [2] is able to output the cuts themselves. This has prompted [2] to raise the natural open question of whether there is an algorithm that releases all-pairs min-cut values with error polynomially smaller than ; the distinction between releasing cuts and releasing only their values has also been noted in [6 CDFZ26].
In this work, we answer this open question in the affirmative, and show how to output all min - cut values with quadratically lower additive error than outputting the cuts themselves.
Theorem 1.1. Let . There exists an -DP algorithm which for any non-negatively weighted vertex graph outputs values for each . If the value of the - min-cut in is , then with probability at least it holds simultaneously over all that
We also give a (much weaker) lower bound, showing that releasing all min - cut values is quantitatively harder than releasing a single min-cut value: Corollary 4.1 shows that, for a natural range of and , every -DP mechanism which outputs all cut values from a fixed source node must incur additive error on some cut value. In contrast, prior works of [6, 2] show that both tasks are equally efficient (both have additive error), if one is also required to release cuts certifying the min-cut values. Notably, our lower bound holds for an easier problem since we fix one end point.
Open Problems. Given the exponential gap between our upper and lower bounds, a natural open problem is to improve the bounds in either direction towards discovering the asymptotically optimal bounds. It is also interesting to ask for improved bounds for the problem of releasing all min - cut values for a fixed public node , the “single-source” version of the problem studied in this work. For this simpler problem, naively applying advanced composition already gives dependence, and we ask if this bound can be improved.
Preliminaries
Let be a weighted graph, where we throughout this paper assume that ; we interpret edges of weight zero as non-edges. For , we use to denote the value of a min cut between and in the graph . We recall some basic DP definitions.
Definition 2.1 (Edge-Neighboring Graphs). Graphs and are called edge-neighboring if there is such that and for all , .
Definition 2.2 (Differential Privacy [9]). A randomized algorithm is -DP if for any neighboring graphs and and any set of possible outcomes of it holds . When , algorithm is called pure DP, or -DP.
Now we describe the version of the sparse vector technique (SVT) that we require for our main algorithm for releasing all pairwise min-cut values under differential privacy. Let be an input space equipped with a neighboring relation . For a scalar query , define its global -sensitivity by
Adaptive threshold queries. We employ an adaptive version of SVT that allows us to approximately answer a sequence of questions of the form “Is ?” for a sequence of scalar queries each of sensitivity at most and a sequence of thresholds . Adaptivity means that the algorithm can choose and based on answers to previous questions. At round , after observing the preceding transcript , the algorithm chooses a new query and a threshold . SVT roughly states that we are able to get accurate answers up to additive error scaling with , where is the total number of Yes answers we will get.
Theorem 2.1 (SVT). Consider any , , and . Consider a private dataset and a sequence of (adaptively chosen) sensitivity $\Delta queries along with a sequence of thresholds . Let
There exists an -DP algorithm which outputs a sequence with across all timesteps
If , then .
If , then .
If , then (the algorithm has already answered Yes times).
This version of the SVT theorem which we use slightly differs from a standard presentation in [8] though follows immediately from the same techniques, we defer its proof to Section A.
Algorithm for DP All-Pairs Min-Cut Values
In this section we prove Theorem 1.1. For simplicity, we first assume that for the graph , is bounded by a polynomial in . At the end of the section, we discuss how to handle arbitrary non-negative edge weight. We start with the following observation.
Observation 3.1. Let be three arbitrary vertices in the graph, and be a real number. If and , then as well.
Proof. Suppose is . Consider the two components of a Min---Cut: and . If , then is an --Cut as well, and so is at most , a contradiction. Similarly, if , then is a --Cut as well and so is at most , a contradiction. So must be at least . □
As in Theorem 2.1, we define
Here, is an upper bound on the number of SVT scalar queries our algorithm will make. We later upper-bound by . In particular, Theorem 2.1 guarantees that under -DP, with probability at least , we can answer up to scalar queries of sensitivity at most one within error as long as the number of Yes answers is at most . Our scalar functions are of the form for disjoint subsets where
Clearly has sensitivity at most one under the notion of edge-neighboring graphs.
Our algorithm consists of many steps each with a different cut threshold. At each step with threshold , the vertices will be decomposed into components, such that if and are in the same component, is at least , and if they are in different components, is smaller than . At step , we lower the threshold and coarsen this decomposition.
At step we start with a high threshold such that the for all and having all components be singletons. By the assumption that the edge weights are polynomially bounded, it suffices to set . Going from step to step , we let .
Suppose at the beginning of step , we have components . We take two arbitrary components and query if is at least . If the answer is Yes, we merge and . We continue until we coarsen the decomposition to many components where for each pair of current components we have performed the above threshold query with answer No.
Lemma 3.1. At step , we perform queries. If the number of Yes queries during step is , then , i.e. the number of components at step is the number of components at step minus the number of YES queries.
Proof. During step , two components can merge at most times, so there are at most distinct components in total that can ever be part of a query, including the initial components and the components created by merging. Since each pair of components is queried at most once during step , the total number of queries during step is at most . Each time we get a YES, the number of components goes down by one which proves the second statement. □
Corollary 3.1. The total number of Yes queries the algorithm asks is at most and the total number of queries is .
Proof. The first statement follows directly from the previous lemma, and the second statement follows since we assumed the weights of and hence is polynomially bounded. □
The next lemma shows that we can approximately recover the values of the min-cuts from the steps at which components merged.
Lemma 3.2. With probability at least , the following holds simultaneously for every step : if and are two components that merge at step , then, for every and , is in .
Proof. Let be the event that all threshold queries are answered within error . Since the total number of Yes queries is at most by Corollary 3.1, it follows from Theorem 2.1 and the way we set that . It thus suffices to show that if occurs, is in deterministically. We use induction on . For , there is nothing to prove. However, note that since all min-cuts in the graph are smaller than , under , no components are merged during step . Assume that and that the result holds for smaller values of .
We first prove the upper bound. Let and be the components containing and , respectively, at the end of step . Since and did not merge during step , the query with threshold was answered with No. Under , this implies that for every pair of nodes and , , and in particular .
It remains to prove that . We prove that, throughout step , any two vertices in the same component have min-cut value at least . This holds at the beginning of step by the induction hypothesis and the fact that the thresholds are decreasing. Now suppose that and were merged during step . Under , this implies that since the query was answered with a Yes. Consequently, there exist and such that . Inductively, all pairs of vertices within , and all pairs within , have min-cut values at least . Since having min-cut at least is an equivalence relation by Observation 3.1, it follows that , as desired. □
We can now prove our main result
Proof of Theorem 1.1. We run the algorithm described above. As weights are nonnegative, when is large enough that , with probability at least , so there is just one component on all nodes left. For any pair of nodes , we note the step in which the components of and are merged and our estimate of is simply . By Lemma 3.2, with probability at least , the error is
Using Corollary 3.1, the number of queries is polynomial in , so it follows that the error is bounded by
The algorithm is -DP as the merge history and hence the estimates are post-processing of the -DP SVT answers.
Handling Unbounded Weights. While we proved our result for polynomially bounded weight functions, there is a simple trick to obtain an algorithm with no such assumption. The idea is to use half the privacy budget to first obtain coarse estimates of all pairwise min-cut values. This can be done by adding independent Laplace noise to each edge weight of and computing the min-cut values on the resulting graph. With probability at least , no edge changes weight by more than , so all cut values are preserved within .
We use the second half of the privacy budget to simulate the algorithm behind Theorem 1.1. However, since we have coarse bounds on the min-cut values, instead of running the threshold queries for every step , we only need to consider steps such that is within of some min-cut value of the graph. Since there are at most different min-cut values in any non-negatively weighted graph [11], the number of steps we need to consider is therefore
and the number of queries is at most a polynomial factor in larger. We thus obtain that . Setting the failure probability of the second algorithm to , a union bound gives that the final algorithm fails with probability at most , and the final error remains unchanged within constant factors.
A Lower Bound for Releasing All-Pairs Min-Cut Values
In this section, we prove an error lower bound for releasing all-pairs min-cut values. The lower bound holds for an easier problem of releasing all the min-cut values from a single fixed source. The main idea is a reduction from the well studied problem of releasing prefix sums, which is classical in differential privacy [7, 5]. We recall its definition below.
Definition 4.1 (DP Prefix-Sum Problem). For a string and , define its prefix sums as . Two strings and are called neighboring if they differ in exactly one coordinate. The DP prefix-sum problem asks to output all the values under this neighboring definition.
A recent work proves the following lower bound [3]. Importantly for our setting, their lower bound holds even in the offline model, in which the mechanism receives the entire string before producing its output.
Theorem 4.1 ([3]). There is a sufficiently small constant such that, for any
every -DP mechanism for the offline prefix-sum problem satisfies
Remark: Here, the condition means that for some fixed constant . The implicit constant in the lower bound may depend on .
We now give a reduction from the problem of Definition 4.1 to releasing all min-cut values from a single fixed source. The main idea in the lemma is to encode prefix sums as min cuts from a single source node, using a modified path graph; we refer to Figure 1.
Figure 1. Example of the lower bound gadget.
Lemma 4.1. For every , there is a simple undirected weighted graph on vertices, with a source and vertices , such that
If and differ in one coordinate, then and differ in the weight of one edge by 1.
Proof. Given a string , we construct the corresponding graph as follows. This is also shown in Figure 1. Let the vertices be and set the source as . First connect the vertices in a path with all edge weights . That is, for each , add the path edge with weight . This is independent of the string . Now to incorporate the string, for each , add the edge with weight . For example, when , the construction is shown in Figure 1.
It is clear that for two neighboring strings in the sense of Definition 4.1, their corresponding graphs differ in exactly one edge by weight one.
Now the important claim is that the min cuts from the source are exactly the prefix sums of the string , up to an additive shift which is known. Indeed, consider the min-cut between and node for some . Let’s imagine the vertices as linearly ordered as shown in Figure 1. Due to our choice of , we never want to cut more than one weight- edge and it is clear that at least one weight- edge must be cut. It is also clear that a weight- edge after must be cut, otherwise there is a path of weight- edges from to . If we cut some weight- edge adjacent to for , then we must also cut all the edges corresponding to (otherwise there is a path from to ), and these additional edges we cut incur cost which is equal to the prefix sum . But since prefix sums are non-decreasing, it never hurts to take , in which case we get the prefix sum , and shifting the index by 1 proves (1).
Consequently, any -DP mechanism for releasing all min-cut values of from the source gives an -DP mechanism for releasing all prefix sums of . Indeed, if we have min cut estimates , we output the prefix sum estimate . This reduction preserves both differential privacy and additive error. This observation along with the reduction of Lemma 4.1 and the prior result of Theorem 4.1 immediately proves the following corollary.
Corollary 4.1. There is a sufficiently small constant such that, for any and , every -DP mechanism that, on an -vertex simple undirected weighted graph with a fixed public source , releases estimates for every must satisfy
There are several interesting remarks to make. The first is that the lower bound holds for the easier problem of releasing all min cut values from a single fixed source, rather than APMC values. It is an interesting question to determine if this is the right answer for the fixed source problem. The second is that the result shows a separation between releasing one fixed min cut value and releasing APMC values. For a single min cut, one can obtain expected error using the Laplace mechanism, whereas APMC values requires error that must grow with the number of vertices. Lastly, the lower bound shows that APMC is a “harder” problem than privately releasing all vertex degrees of a graph (which are perhaps the most natural overestimates of the true min cut values), since degrees can be released with error.
Declaration of AI Use
The lower bound of Corollary 4.1 was derived by ChatGPT 5.6 Pro when the authors prompted it with a prior weaker lower bound based on the packing argument. The writing was heavily edited by the authors and the authors assume responsibility for all content.
Proof of SVT Theorem
We give a proof of a slightly non-standard utility theorem for the Sparse Vector Technique (SVT). This follows immediately from standard analysis found in [8] but is not precisely the theorem stated there. For completeness, we include the proof here.
Background from [8]. Consider the AboveThreshold algorithm (Algorithm 1 in [8]), which takes in a private dataset , a privacy parameter , a sequence of (adaptively chosen) sensitivity 1 queries, and a threshold . After receiving each query, the algorithm either outputs No and continues to the next query or outputs Yes and halts, it answers no more queries after this point. Let be the output after receiving query . In Theorem 3.23 of their work, the authors prove that this algorithm -DP.
Lemma A.1. AboveThreshold is -DP.
Within the proof of Theorem 3.25 of their work (which is not exactly what we want), the authors use the Laplace tail bound and a union bound to show the following statement.
Lemma A.2. Let
Then, with probability , the following holds across all timesteps:
If , then .
If , then .
Finally, for our proof, we need the advanced composition theorem, appearing as Corollary 3.21 in their work.
Theorem A.1. For all and , -fold adaptive composition of -DP mechanisms satisfies -DP as long as
Now, we are ready to prove the version of SVT theorem we use.
Theorem 2.1 (SVT). Consider any , , and . Consider a private dataset and a sequence of (adaptively chosen) sensitivity queries along with a sequence of thresholds . Let
There exists an -DP algorithm which outputs a sequence with such that the following holds with probability across all timesteps
If , then .
If , then .
If , then (the algorithm has already answered Yes times).
Proof. We implement SVT by composition of at most calls to AboveThreshold. We normalize and recenter all queries for SVT to for AboveThreshold with a fixed threshold . When a call to AboveThreshold returns No, SVT will return No. When a call to AboveThreshold returns Yes and halts, SVT will return Yes and instantiate a fresh call to AboveThreshold if the number of Yes outputs is less than . Otherwise, SVT will return Halt for the remainder of time.
Let . Note that SVT’s only interaction with the private dataset is via the outputs of at most instantiations of AboveThreshold. Using as the privacy parameter for each call to AboveThreshold, SVT is -DP by Lemma A.1 and Theorem A.1.
The utility of SVT follows from that of AboveThreshold via Lemma A.2 plugging in and in order to union bound over the failure probability of each call to AboveThreshold. Lemma A.2 gives additive error
Since AboveThreshold operates on the normalized queries , the additive error term in the final theorem statement has an additional factor .
References
- [1]Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Breaking the n^{1.5} additive error barrier for private and efficient graph sparsification via private expander decomposition. In Forty-second International Conference on Machine Learning, 2025. ↑2arxiv.org/abs/2507.01873
- [2]Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Yuriy Nevmyvaka, Sandeep Silwal, and Yinzhan Xu. Differentially private gomory-hu trees. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. ↑2arxiv.org/abs/2408.01798
- [3]Konstantina Bairaktari and Kasper Green Larsen. The binary tree mechanism is optimal for approximate differentially private continual counting. arXiv preprint arXiv:2607.00876, 2026. ↑6, ↑7arxiv.org/abs/2607.00876
- [5]T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1–24, 2011. ↑6
- [6]Mina Dalirrooyfard, Slobodan Mitrović, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. Advances in Neural Information Processing Systems, 36:24947–24965, 2023. ↑2DOI
- [7]Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724, 2010. ↑6DOI
- [8]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. ↑4, ↑10
- [9]Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006. ↑3
- [10]Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–578. SIAM, 2020. ↑2
- [11]Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961. ↑6DOI
- [12]Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1106–1125. SIAM, 2010. ↑2
- [13]Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of cryptography conference, pages 339–356. Springer, 2012. ↑2
- [14]Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman. Privately solving linear programs. In International Colloquium on Automata, Languages, and Programming, pages 612–624. Springer, 2014. ↑2DOI
- [15]Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019–1049. SIAM, 2024. ↑2arxiv.org/abs/2309.17330
