Query Lower Bounds for Correlation Clustering under Memory Constraints
For researchers in graph algorithms and clustering, this provides the first lower bounds for correlation clustering under memory constraints, though some bounds are not tight.
This paper initiates the study of memory-query tradeoffs for correlation clustering, proving a tight query lower bound of Ω(n/ε²) for additive εn² approximation, and showing that under memory constraints, even approximating the optimal cost requires more than n/ε² queries in the random query model.
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.