CKR Partitions and Lower Bounds for Constrained Correlation Clustering and Variants

Abstract

By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two; minimum weakness strong triadic closure, cluster deletion and constrained correlation clustering. Additionally, we analyze the well-known low-diameter decomposition by Calinescu, Karloff and Raban applied to the standard LP relaxation semi-metric for constrained correlation clustering. As opposed to traditional pivot-based approaches, a CKR partition elegantly handles must-link and cannot-link constraints. It guarantees a 3-approximation in expectation, which matches the original approximation ratio by van Zuylen and Williamson. We conjecture that it in fact achieves a strictly better than 3-approximation, yet this remains an open problem.

Independent and concurrent of our work, both Cao and Xu~\cite{cao2026cluster} and Azizeddin et al.~\cite{azizeddin2026constrained} obtained the same hardness results for CD and CCC