Private graph colouring with limited defectiveness
<|reference_start|>Private graph colouring with limited defectiveness: Differential privacy is the gold standard in the problem of privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most fundamental questions about a graph. In this paper, we study the vertex colouring problem in the differentially private setting.   To be edge-differentially private, a colouring algorithm needs to be defective: a colouring is d-defective if a vertex can share a colour with at most d of its neighbours. Without defectiveness, the only differentially private colouring algorithm needs to assign n different colours to the n different vertices. We show the following lower bound for the defectiveness: a differentially private c-edge colouring algorithm of a graph of maximum degree {\Delta} > 0 has defectiveness at least d = {\Omega} (log n / (log c+log {\Delta})).   We also present an {\epsilon}-differentially private algorithm to {\Theta} ( {\Delta} / log n + 1 / {\epsilon})-colour a graph with defectiveness at most {\Theta}(log n).<|reference_end|>
@article{christiansen2024private,
    title={Private graph colouring with limited defectiveness},
    author={Aleksander B. G. Christiansen, Eva Rotenberg, Teresa Anna Steiner,
  Juliette Vlieghe},
    journal={arXiv preprint arXiv:2404.18692},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.18692},
    primaryClass={cs.DS}
}