# Differentially Private Matchings

arXiv: https://arxiv.org/abs/2501.00926 · HTML: https://mlsanity.com/paper/2501.00926/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jan 2025.

## Built on by (most cited first, 1 of 1)

- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)

## Abstract (arXiv)

Computing matchings in graphs is a foundational algorithmic task. Despite extensive interest in differentially private (DP) graph analysis, work on privately computing matching solutions, rather than just their size, has been sparse. The sole prior work in the standard model of pure varepsilon-differential privacy, by Hsu, Huang, Roth, Roughgarden, and Wu [HHR+14, STOC'14], focused on allocations and was thus restricted to bipartite graphs. We present a comprehensive study of DP algorithms for maximum matching and b-matching in general graphs, which also yields techniques that improve upon the bipartite setting. En route to solving these matching problems, we develop a set of novel techniques with broad applicability, including a new symmetry argument for DP lower bounds, the first arboricity-based sparsifiers for node-DP, and the novel Public Vertex Subset Mechanism.