Differentially Private Multiway and $k$-Cut
<|reference_start|>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(k\log 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 $\widetilde{O}(k^{1.5})$.<|reference_end|>
@article{chandra2024differentially,
    title={Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism
  Approach and More},
    author={Rishi Chandra and Michael Dinitz and Chenglin Fan and Zongrui Zou},
    journal={arXiv preprint arXiv:2407.06911},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.06911},
    primaryClass={cs.CR cs.DS}
}