Differentially Private Matchings

Computing matchings in general graphs plays a central role in graph algorithms. However, despite the recent interest in differentially private graph algorithms, there has been limited work on private matchings. Moreover, almost all existing work focuses on estimating the size of the maximum matching, whereas in many applications, the matching itself is the object of interest. There is currently only a single work on private algorithms for computing matching solutions by [HHRRW STOC'14]. Moreover, their work focuses on allocation problems and hence is limited to bipartite graphs. Motivated by the importance of computing matchings in sensitive graph data, we initiate the study of differentially private algorithms for computing maximal and maximum matchings in general graphs. We provide a number of algorithms and lower bounds for this problem in different models and settings. We first prove a lower bound showing that computing explicit solutions necessarily incurs large error, even if we try to obtain privacy by allowing ourselves to output non-edges. We then consider implicit solutions, where at the end of the computation there is an ($\varepsilon$-differentially private) billboard and each node can determine its matched edge(s) based on what is written on this publicly visible billboard. For this solution concept, we provide tight upper and lower (bicriteria) bounds, where the degree bound is violated by a logarithmic factor (which we show is necessary). We further show that our algorithm can be made distributed in the local edge DP (LEDP) model, and can even be done in a logarithmic number of rounds if we further relax the degree bounds by logarithmic factors. Our edge-DP matching algorithms give rise to new matching algorithms in the node-DP setting by combining our edge-DP algorithms with a novel use of arboricity sparsifiers. [...]
Comment: Abstract truncated to fit arXiv limits