CS Paper Radar

Differentially Private All-Pairs Min Cut Values

Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard, Slobodan Mitrović, Sandeep Silwal, Yinzhan Xu

cs.DS ·submitted 2026-11-05 19:54 UTC · v1
publishedtheory

Abstract

We study the problem of privately releasing the min cut values of all pairs of vertices in a given $n$-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 $\tilde{O}(n)$ additive error. Prior works [Dalirrooyfard, Mitrovi{ć} and Nevmyvaka, 2023; Aamand et al., 2026] have established that $\tildeΘ(n)$ 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 $\tilde{O}(n)$ bound. In this work, we give an approximate DP algorithm outputting all-pair min cut values with $\tilde{O}(\sqrt{n})$ 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 $Ω(\log^{3/2} n)$ lower bound for this problem.

Comment
To appear in SOSA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

cs.DS cs.CR ·2026-09-09 ·Jacob Imola, Rasmus Pagh, Lukas Retschmeier
top venuetheory similarity 0.68
Abstract · 32 pages, 3 figures. To appear at PODS 2027

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

0.60

Finding and Certifying Weighted Minimum Cuts with Cut Queries

cs.DS ·2026-11-02 ·Troy Lee
similarity 0.67
Abstract · 57 pages. v2: corrects cross-reference names (some lemmas, remarks, definitions and corollaries were labelled "Theorem"); no change in conte…

We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.

0.25

Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries

cs.DS ·2026-10-16 ·Yotam Kenneth-Mordoch
published similarity 0.67
Abstract · Accepted at SOSA 2027

Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $δ$.

0.28

Tight Bounds for Differentially Private Cut Release

cs.DS ·2026-11-14 ·Chenghua Liu, Boning Meng
theory similarity 0.66
Abstract · 24 pages

We give a polynomial-time algorithm for releasing a nonnegative weighted synthetic graph under $(\varepsilon,δ)$-edge differential privacy. Given an $n$-vertex nonnegative weighted graph $G=(V,w_G)$, the output $H=(V,w_H)$ satisfies, with probability at least $1-β$, simultaneously for every $S\subseteq V$, $|w_G(S,V\setminus S)-w_H(S,V\setminus S)| \leγw_G(S,V\setminus S)+O\bigl((n\log n)/(\varepsilonγ)\bigr)$, provided that $γ,\varepsilon,δ,β$ are at least inverse polynomial in $n$. For constant $γ,\varepsilon$ and $δ=β=n^{-10}$, this improves the recently obtained additive error bound of $O(n\log^7 n)$ to $O(n\log n)$. We also prove a matching $Ω(n\log n)$ lower bound. Our algorithm combines degree decomposition with private multiplicative weights, using a degree-sensitive semidefinite oracle to generate update proposals from single Gaussian samples. Each proposal is validated by a noisy check of its exact entropy decrease, and a joint Rényi analysis of sampling and validation avoids additional logarithmic losses.

0.06

Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error

cs.DS math.ST ·2026-11-04 ·Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu +5 more
theory similarity 0.64
Abstract

We give a polynomial-time $(\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$. Our algorithm outputs a nonnegative weighted graph $H$ such that, with probability at least $1-β$, simultaneously for all $S\subseteq V$, \[ \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right| \leq γw_G(S,V\setminus S) + O\left(\frac{n}{γ\varepsilon} \log^7 \frac{n}{δβγ\varepsilon}\right). \] For fixed $γ, \varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \operatorname{polylog} n$, improving upon the previous efficient bound of $n^{13/12 + o(1)}$. Furthermore, we establish an $Ω(n/γ\varepsilon)$ lower bound for the relevant parameter regime, showing that our result is tight up to polylogarithmic factors. Our algorithm uses a log-det-regularized SDP to generate fractional queries for multiplicative-weights updates and certify accuracy for all cuts. The privacy analysis charges privacy loss only fractionally per mechanism call, based on the amount of mass on edge coordinates retired from subsequent iterations. Our synthetic graph release yields improved error bounds for several downstream tasks in private graph analysis including correlation clustering, Max-Cut, Max-$k$-Cut, constrained cut problems and hierarchical clustering. Most notably, for unweighted complete-graph correlation clustering, we achieve the optimal $\widetilde O(n)$ additive error while reducing the best previously known approximation ratio for this additive error from several thousand to $1.387$. We also provide a formalization of our results in Lean.

0.53

Directed Global Minimum Cut in Almost-Linear Time

cs.DS ·2026-10-07 ·Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
highly cited similarity 0.63
Abstract · 11 pages, 4 figures

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving the previous $m^{1+o(1)}\min\{\sqrt{n},n/m^{1/3}\}$ bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a $(1+ε)$-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after $O(\log n)$ rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.

0.48

The Power of Interaction in Locally Edge-Private Subgraph Counting

cs.DS cs.CR ·2026-11-03 ·Xian Chen, Pan Peng
theory similarity 0.63
Abstract · 64 pages

We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph $H$ with $k$ vertices, $\ell\ge1$ edges, and $q$ connected components, our goal is to approximately count its copies in an arbitrary $n$-vertex undirected graph while preserving edge privacy. We give two complementary accuracy guarantees. First, for every $H$, we give Linear Noise Cancellation (LNC), a two-round $\varepsilon$-LEDP algorithm with additive error and root mean square error both $O(n^{k-3/2}/\varepsilon^\ell)$ on every $n$-vertex graph. For fixed sufficiently small $\varepsilon$, this improves the optimal noninteractive additive error for triangles by a factor of $\sqrt n$ and gives the same improvement in worst-case root mean square error for all cliques on at least three vertices. To our knowledge, this is the first separation between interactive and noninteractive LEDP subgraph counting, showing that a single additional round can improve worst-case accuracy polynomially. Second, we determine how accuracy improves when the graph has maximum degree at most a public bound $d$. Our Predict and Correct (PC) framework gives an $(\ell+2)$-round $\varepsilon$-LEDP algorithm with additive error $O(n^{q-1/2}d^{k-q-1}\log^{3\ell-2}n/\varepsilon^\ell)$. For connected patterns, its polynomial factor is $\sqrt n\,d^{k-2}$, giving sublinear error on constant-degree graphs at fixed privacy. We prove matching lower bounds in $n$ and $d$, up to logarithmic factors at fixed privacy, even under arbitrary interaction and approximate privacy with sufficiently small $δ$. At $d=Θ(n)$, the lower bound also establishes the optimality of LNC's dependence on $n$.

0.21

Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs

cs.DS ·2026-08-17 ·Jason Li, Trevor Vaughn
similarity 0.63
Abstract

The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\varepsilon)k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give the first $\widetilde O_k(n^{ck})$-time algorithm for Minimum $k$-Cut on simple graphs for an absolute constant $c<1$. More precisely, the running times are $\widetilde O(n^2)$ for $k=3$, $\widetilde O(n^{55/19})$ for $k=4$, and $\widetilde O(n^{4.112007})$ for $k=5$; for every $k\ge6$, the running time is \[ k^{O(k^2)}n^{1+(6k-6)\frac{k-1.749614}{7k-10}}(\log n)^{O(k^2)}, \] whose exponent is $\frac67k-0.132\ldots+O(1/k)$. The algorithm combines three ingredients. First, for weighted Minimum $k$-Cut we give a randomized \[ k^{O(k^2)}n^{k-2}(m+n)\log^3(n) \] -time algorithm: it perturbs the edge weights so that any minimum $k$-cut has a side with boundary strictly smaller than average. These then cut few edges of some tree in a logarithmic-size sample from a tree packing with high probability. After we enumerate them, we recursively compute $(k-1)$-cuts to complete them to the $k$-cuts of which they were a part. A variant of the perturbation and processing the entire packing support give a deterministic $k^{O(k^2)}n^{k+O(1)}$-time variant. Second, for cut size $s$, we give an improved FPT algorithm using a near-linear-time construction of an $(O(s\log^2 n\log\log n),s)$ edge-unbreakable tree decomposition with $O(s\log^2 n\log\log n)$ adhesion; this also gives a near-linear-time approximation algorithm for Minimum $k$-Cut. Third, we refine the border/island framework of~\cite{HL22}, using rectangular matrix multiplication to recover singleton islands and balancing it against the improved FPT algorithm.

0.36