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

CREATORFlorian Adriaens, Nikolaj Tatti
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-04463

Browse the full library · About the Tower of Babel