Differentially Private Multiway and k-Cut

In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the minimum k-cut and multiway cut problems. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. For the multiway cut problem, we first provide a private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm. We then present a tight information-theoretic lower bound on the additive error, demonstrating that our algorithm on weighted graphs is near-optimal for constant k. For the minimum k-cut problem, our algorithms leverage a known bound on the number of approximate k-cuts, resulting in a private algorithm with optimal additive error O(klog n) for fixed privacy parameter. We also establish a information-theoretic lower bound that matches this additive error. Additionally, we give an efficient private algorithm for k-cut even for non-constant k, including a polynomial-time 2-approximation with an additive error of O(k1.5).