Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering

Florian Adriaens, Nikolaj Tatti
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:675-689, 2026.

Abstract

The Bad Triangle Transversal (BTT) problem asks for the smallest set of edges that need to be removed from a given signed graph, so that the resulting graph does not have a bad triangle. Here, a bad triangle is a triangle with exactly one negative edge. Several 2-approximations for BTT are proposed in this paper. On the hardness side, we show that BTT is NP-hard to approximate with factor better than $\frac{2137}{2136}$ on complete graphs. Our reduction also works for Correlation Clustering (CC), the Cluster Deletion problem (CD) and the Minimum Strong Triadic Closure problem (MinSTC). Lastly, we show that the BTT and CC optima are within a factor of 3/2 in complete graphs, by describing a pivot procedure that transforms transversals into clusters.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-adriaens26a, title = {Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering}, author = {Adriaens, Florian and Tatti, Nikolaj}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {675--689}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/adriaens26a/adriaens26a.pdf}, url = {https://proceedings.mlr.press/v306/adriaens26a.html}, abstract = {The Bad Triangle Transversal (BTT) problem asks for the smallest set of edges that need to be removed from a given signed graph, so that the resulting graph does not have a bad triangle. Here, a bad triangle is a triangle with exactly one negative edge. Several 2-approximations for BTT are proposed in this paper. On the hardness side, we show that BTT is NP-hard to approximate with factor better than $\frac{2137}{2136}$ on complete graphs. Our reduction also works for Correlation Clustering (CC), the Cluster Deletion problem (CD) and the Minimum Strong Triadic Closure problem (MinSTC). Lastly, we show that the BTT and CC optima are within a factor of 3/2 in complete graphs, by describing a pivot procedure that transforms transversals into clusters.} }
Endnote
%0 Conference Paper %T Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering %A Florian Adriaens %A Nikolaj Tatti %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-adriaens26a %I PMLR %P 675--689 %U https://proceedings.mlr.press/v306/adriaens26a.html %V 306 %X The Bad Triangle Transversal (BTT) problem asks for the smallest set of edges that need to be removed from a given signed graph, so that the resulting graph does not have a bad triangle. Here, a bad triangle is a triangle with exactly one negative edge. Several 2-approximations for BTT are proposed in this paper. On the hardness side, we show that BTT is NP-hard to approximate with factor better than $\frac{2137}{2136}$ on complete graphs. Our reduction also works for Correlation Clustering (CC), the Cluster Deletion problem (CD) and the Minimum Strong Triadic Closure problem (MinSTC). Lastly, we show that the BTT and CC optima are within a factor of 3/2 in complete graphs, by describing a pivot procedure that transforms transversals into clusters.
APA
Adriaens, F. & Tatti, N.. (2026). Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:675-689 Available from https://proceedings.mlr.press/v306/adriaens26a.html.

Related Material