Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.23104 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913154552823808 |
|---|---|
| author | Garg, Sumegha He, Songhua Papakonstantinou, Periklis A. |
| author_facet | Garg, Sumegha He, Songhua Papakonstantinou, Periklis A. |
| contents | This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non-edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of $\varepsilon n^2$, any algorithm requires $Ω(n/\varepsilon^2)$ adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make $\gg n/\varepsilon^2$ adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23104 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Query Lower Bounds for Correlation Clustering under Memory Constraints Garg, Sumegha He, Songhua Papakonstantinou, Periklis A. Computational Complexity This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non-edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of $\varepsilon n^2$, any algorithm requires $Ω(n/\varepsilon^2)$ adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make $\gg n/\varepsilon^2$ adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results. |
| title | Query Lower Bounds for Correlation Clustering under Memory Constraints |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.23104 |