Correlation Clustering via s-Club Cluster Edge Deletion

Abstract

Cluster Editing, a known model for correlation clustering, has garnered significant consideration in the parameterized complexity area and has been utilized in a range of practical contexts. In certain situations, the requirement for clusters to be cliques was deemed excessively stringent, leading to the proposal of alternative relaxed clique models for dense subgraphs, such as s-club. In this work, we implement three approaches to tackle the 2-club clustering via edge deletion: a heuristic approach based on the influence of the edge to resolve maximum conflicts, a parameterized algorithm in which by deleting a maximum of k edges, the graph can be transformed into a 2-club cluster based on a branching algorithm, and the approach in Integer Linear Programming to find the optimized solution in an integer formulation. We run these algorithms and cross-compare the three experiment results to the fastest Cluster Editing algorithm which runs in O(1.62k) time. Our 2-club Cluster Edge Deletion approach showed better performance than Cluster Editing in terms of running time, and significantly less cost of modifications while preserving the information of the underlying structure. Finally, we consider the 3-clubs Cluster Edge Deletion which did not have much focus in the literature. The problem can be solved in time O(4k). We present a first fixed-parameter algorithm that breaks this 4k barrier by solving the problem in O(3.65k) time. In addition, we implement this 3CCED algorithm in the heuristic approach and compare the experiments to Cluster Editing and 2CCED. The results show that the 3-club Cluster Edge Deletion presents the highest performance in terms of running time and cost of modifications to reach the desired results. This shows that deletion into a graph whose components are of bounded diameter can be a better model for correlation clustering.