Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

Jacob Imola, Rasmus Pagh, Lukas Retschmeier

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}…