Abstract: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 $\Omega(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.
| Comments: | accepted by ITCS 2026 |
| Subjects: | Computational Complexity (cs.CC) |
| Cite as: | arXiv:2605.23104 [cs.CC] |
| (or arXiv:2605.23104v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23104 arXiv-issued DOI via DataCite (pending registration) |
From: Songhua He [view email]
[v1]
Thu, 21 May 2026 23:50:12 UTC (402 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。