Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2404.18692 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911137501544448 |
|---|---|
| author | Christiansen, Aleksander B. G. Rotenberg, Eva Steiner, Teresa Anna Vlieghe, Juliette |
| author_facet | Christiansen, Aleksander B. G. Rotenberg, Eva Steiner, Teresa Anna Vlieghe, Juliette |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18692 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Private graph colouring with limited defectiveness Christiansen, Aleksander B. G. Rotenberg, Eva Steiner, Teresa Anna Vlieghe, Juliette Data Structures and Algorithms 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). |
| title | Private graph colouring with limited defectiveness |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.18692 |