Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs

The Maximum Balanced Biclique Problem is a relevant graph model with a number of applications in diverse domains. However, the problem is NP-hard and thus computationally challenging. In this paper, we introduce a novel metaheuristic algorithm, which combines an effective constraint-based tabu search procedure and two dedicated graph reduction techniques. We verify the effectiveness of the algorithm on 30 classical random benchmark graphs and 25 very large real-life sparse graphs from the popular Koblenz Network Collection (KONECT). The results show that the algorithm improves the best-known results (new lower bounds) for 10 classical benchmarks and obtains the optimal solutions for 14 KONECT instances.