Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2404.18692 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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).