Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering

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.

Imagine a social network where people are either friends or foes. Prior research has shown how to efficiently group these people into clusters where, generally speaking, members of the same group are friends, while people in different groups are foes. But can we also achieve this goal by only resolving local conflicts, meaning we only focus on eliminating situations where a friend of a friend is a foe? We demonstrate that by removing these local conflicts (the Bad Triangle Transversal problem), we can approximate the global clustering question (the Correlation Clustering problem). We introduce several novel approximation algorithms and theoretical limits for both challenges, and prove that their optimal solutions are intricately linked. These methods apply to any scenario requiring clustering or conflict resolution based on pairwise similarity. This includes practical applications in fields such as bioinformatics, document clustering, and computer vision.