Private Graph Colouring with Limited Defectiveness

Differential privacy is the gold standard for privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most fundamental graph problems. In this work, we study vertex colouring in the differentially private setting. We consider edge-differential privacy, in which the edges of the graph are the private information that should be protected. To satisfy non-trivial privacy guarantees under this notion of privacy, 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, any edge-differentially private colouring algorithm needs to assign n different colours to the n different vertices. We show the following lower bound for the defectiveness: any ϵ-edge differentially private algorithm that returns a c-vertex colouring of a graph of maximum degree Δ>0 with high probability must have defectiveness at least d∈Ω(logn/(ϵ+logc)). We complement our lower bound by presenting an ϵ-differentially private algorithm for O(Δ/logn+ϵ^-1)-colouring a graph with defectiveness at most O(logn).