2026-07-22T06:48:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25354 2026-03-19T13:03:56Z ddc:004 open_access

Query Lower Bounds for Correlation Clustering Under Memory Constraints Garg, Sumegha He, Songhua Papakonstantinou, Periklis A. correlation clustering query-space complexity information theory 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 ε n², any algorithm requires Ω(n/ε²) 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 ≫ n/ε² 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sumegha Garg and Songhua He and Periklis A. Papakonstantinou 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.67 urn:nbn:de:0030-drops-253542 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.67 eng https://creativecommons.org/licenses/by/4.0/legalcode