Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.04463 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913165006077952 |
|---|---|
| author | Adriaens, Florian tatti, Nikolaj |
| author_facet | Adriaens, Florian tatti, Nikolaj |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04463 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering Adriaens, Florian tatti, Nikolaj Data Structures and Algorithms 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. |
| title | Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.04463 |