2024/04/29 by Aleksander B. G. Christiansen, Christiansen, Aleksander B. G., Eva Rotenberg +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Business #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph #Mathematics
paper · pdf · doi:10.48550/arxiv.2404.18692
openalex publication_date 2024/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ > 0 has defectiveness at least d = Ω (log n / (log c+log Δ)). We also present an ε-differentially private algorithm to Θ ( Δ / log n + 1 / ε)-colour a graph with defectiveness at most Θ(log n).