Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More

Rishi Chandra, Michael Dinitz, Chenglin Fan +1

In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum $k$-cut. We introduce edge-d…