Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering

We consider the classic correlation clustering problem: Given a complete graphs where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the number of the + edges across parts plus the number of the - edges within parts.

Recently, Cohen-Addad, Lee and Newman [FOCS’22] showed the first 1.995-approximation for the problem using the Sherali-Adams hierarchy hence breaking through the integrality gap of 2 of the clas- sic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev [STOC’15].

We significantly improve the result by providing a 1.73-approximation for the problem, making a significant step below 2. Our approach brings together a new preprocessing of correlation clustering instances that enables a new LP formulation which combined with the approach of Cohen-Addad, Lee and Newman [FOCS’22] and a new rounding method yields the improved bound.