Understanding the Cluster Linear Program for Correlation Clustering

In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla [BBC04], the input is a complete graph where edges are labeled either + or -, and the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15] gave a 2.06-approximation by providing a near-optimal rounding of the standard LP, and Cohen-Addad, Lee, Li, and Newman [CLN22, CLLN23] finally bypassed the integrality gap of 2 for this LP giving a 1.73-approximation for the problem.

While introducing new ideas for Correlation Clustering, their algorithm is more complicated than typical approximation algorithms in the following two aspects: (1) It is based on two different relaxations with separate rounding algorithms connected by the round-or-cut procedure. (2) Each of the rounding algorithms has to separately handle seemingly inevitable correlated rounding errors, coming from correlated rounding of Sherali-Adams and other strong LP relaxations [GS11, BRS11, RT12].

In order to create a simple and unified framework for Correlation Clustering similar to those for typical approximate optimization tasks, we propose the cluster LP as a strong linear program for Correlation Clustering. It is exponential-sized, but we show that it can be (1 + ε)-approximately solved in polynomial time for any ε > 0, providing the framework for designing rounding algorithms without worrying about correlated rounding errors; these errors are handled uniformly in solving the relaxation.

We demonstrate the power of the cluster LP by presenting new rounding algorithms, and providing two analyses, one analytically proving a 1.56-approximation and the other solving a factor-revealing SDP to show a 1.485-approximation. Both proofs introduce principled methods by which to analyze the performance of the algorithm, resulting in a significantly improved approximation guarantee.

Finally, we prove an integrality gap of 4/3 for the cluster LP, showing our 1.485-upper bound cannot be drastically improved. Our gap instance directly inspires an improved NP-hardness of approximation with a ratio 24/23 ≈ 1.042; no explicit hardness ratio was known before.

• The conference version of this paper [CCL + 24] claimed an approximation ratio of 1.437 whose proof currently has a gap. This version fixes the gap with a slightly worse approximation ratio of 1.485.