Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
This work provides theoretical insights and approximation algorithms for a problem related to signed graph analysis, with implications for correlation clustering and related problems.
The paper proposes several 2-approximation algorithms for the Bad Triangle Transversal problem and proves it is NP-hard to approximate within a factor better than 2137/2136 on complete graphs. It also shows that the optima of BTT and Correlation Clustering are within a factor of 3/2 in complete graphs.
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.