Simple 2-approximations for bad triangle transversals and some hardness results for related problems
Florian Adriaens, Nikolaj Tatti · 2026
Read Simple 2-approximations for bad triangle transversals and some hardness results for related problems by Florian Adriaens, Nikolaj Tatti (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04463.txt.
Description
Florian Adriaens and Nikolaj Tatti study a graph problem in a 2026 paper on bad triangles. In a signed graph, edges can be positive or negative. A bad triangle has exactly one negative edge, and the task is to remove as few edges as possible to eliminate all such triangles.
The authors give several simple methods that come within a factor of two of the best possible answer. They also prove the problem is hard to approximate beyond a very small margin. Their hardness result extends to related problems, including correlation clustering. They further show that the optima for two of these problems stay within a modest factor on complete graphs.
Catalog record
| CREATOR | Florian Adriaens, Nikolaj Tatti |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-04463