Neighborhood search-based heuristic for the k-clustering minimum biclique completion problem

In this paper, we propose the neighborhood search-based heuristic to solve the k-clustering minimum biclique completion problem. The KCmBCP consists in partitioning a bipartite undirected graph into k clusters such that the total number of edges that added for complete each cluster into a biclique is minimum. Given a bipartite graph G = (S, T, E), we consider the problem of finding k bipartite sub-graphs, called clusters, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to make each cluster complete is minimized. This problem is known as k-clustering minimum biclique completion problem (noted KCmBCP) and has been shown strongly NP-hard. The proposed approach begins by construction of an initial solution. After, the proposed approach enters on iterative phase, which destroys part of the initial solution and build of a feasible solution by exploring the neighborhood of the current solution. The experimental results show the effectiveness of the proposed approach.