Metraipolis › archive › dc_e845f0585f8f
Constrained Correlation Clustering: Towards Optimality — arXiv:2608.05700
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.05700
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T10:50:17.788Z
- SHA-256 of the archived text
61e9f364a15eb468d9c6645836a0d4c35c30c6a74d0b603d0775b8bac149e800- Stable URL of this page
https://metraipolis.com/documento/dc_e845f0585f8f
How to cite
Constrained Correlation Clustering: Towards Optimality — arXiv:2608.05700 — arXiv (en), https://arxiv.org/abs/2608.05700 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e845f0585f8f (Metraipolis archive dc_e845f0585f8f, sha256 61e9f364a15eb468d9c6645836a0d4c35c30c6a74d0b603d0775b8bac149e800)
BibTeX
@misc{dce845f0585f8f,
title = {Constrained Correlation Clustering: Towards Optimality — arXiv:2608.05700},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.05700},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e845f0585f8f; sha256 61e9f364a15eb468d9c6645836a0d4c35c30c6a74d0b603d0775b8bac149e800},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05700. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the number of violated pairs (edges across different clusters plus non-edges within clusters). In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. In this work, we identify Constrained Correlation Clustering as a variant of Correlation Clustering for which optimal approximations might be within reach, and make progress towards this front. Constrained Correlation Clustering is APX-Hard, and the optimal approximation factor is known to lie in $(\frac{24}{23},3]$. We significantly tighten this gap, by showing that the optimal approximation factor lies in $[2,\frac{16}{7}-\gamma)$ for a small constant $\gamma>0$. Our lower bound of $2$ shows a separation between Correlation Clustering (which admits an $1.485+\epsilon$ approximation) and Constrained Correlation Clustering\footnote{The same hardness result was obtained independently by Cao and Xu~\cite{cao2026clusterdeletionhardapproximate}.}. Our upper bound of $\frac{16}{7}-\gamma$ uses the Sherali-Adams relaxation and goes beyond straightforward Triangle-Based analysis; more precisely, our algorithm belongs to a natural class of pivoting algorithms for which we prove that a straightforward Triangle-Based analysis cannot prove a better-than-$\frac{16}{7}$ approximation. Finally, as a byproduct of our techniques, we completely resolve the approximability of Cluster Deletion. Cluster Deletion is a well-studied special case of Constrained Correlation Clustering for which a $2$-approximation algorithm is known. We show that this is optimal, as our lower bound holds even for this special case.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-07 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.05700 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T10:37:54.268Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).