Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

Sepehr Assadi, Chen Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for n-vertex (+/−)-labeled graphs G: A sublinear-time algorithm that with high probability returns a constant approximation clustering of G in O(n log2 n) time assuming access to the adjacency list of the (+)-labeled edges of G (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee. A semi-streaming algorithm that with high probability returns a constant approximation clustering of G in O(n log n) space and a single pass over the edges of the graph G (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with o(n2) space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest.

Original languageEnglish (US)
Title of host publication13th Innovations in Theoretical Computer Science Conference, ITCS 2022
EditorsMark Braverman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772174
DOIs
StatePublished - Jan 1 2022
Event13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States
Duration: Jan 31 2022Feb 3 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume215
ISSN (Print)1868-8969

Conference

Conference13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Country/TerritoryUnited States
CityBerkeley
Period1/31/222/3/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Correlation clustering
  • Semi-streaming algorithms
  • Sublinear algorithms
  • Sublinear time algorithms

Fingerprint

Dive into the research topics of 'Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions'. Together they form a unique fingerprint.

Cite this