Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds

In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to partition the entities into clusters to minimize the number of disagreements with the labels. Currently, all efficient parallel algorithms have an approximation ratio of at least 3. In comparison with the 1.994 + ǫ ratio achieved by polynomial-time sequential algorithms [CLN22], a significant gap exists.

We propose the first poly-logarithmic depth parallel algorithm that achieves a better approximation ratio than 3. Specifically, our algorithm computes a (2.4 + ǫ)-approximate solution and uses Õ(m 1.5 ) work. Additionally, it can be translated into a Õ(m 1.5 )-time sequential algorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with Õ(m 1.5 ) total memory.

Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12] length-constrained multi-commodity flow algorithm, where we develop an efficient parallel algorithm to solve a truncated correlation clustering linear program of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution of the truncated linear program can be rounded with a factor of at most 2.4 loss by using the framework of [CMSY15]. Such a rounding framework can then be implemented using parallel pivot-based approaches (e.g. [BFS12, FN20]).