A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem

Let $$G=(V, E)$$ G = ( V , E ) be a graph with vertex set V and edge set E, and consider $$\gamma \in [0,1)$$ γ ∈ [ 0 , 1 ) to be a real constant. A $$\gamma $$ γ -clique (or quasi-clique) is a subset $$V'\subseteq V$$ V ′ ⊆ V inducing a subgraph of G with edge density at least $$\gamma $$ γ . In this paper, we tackle the minimum quasi-clique partitioning problem (MQCPP), which consists of obtaining a minimum-cardinality partition of V into quasi-cliques. We propose a biased random-key genetic algorithm (BRKGA) relying on an efficient partitioning decoder that allows merge operations to combine smaller quasi-cliques into larger ones. Furthermore, we show that MQCPP and the problem of covering the graph with a minimum number of quasi-cliques are not equivalent. Computational experiments indicate that the proposed BRKGA is very effective in obtaining high-quality solutions for MQCPP in low computational times. More specifically, it can at least match all the best solutions available in the literature, strictly improving over them for 20.3% of the benchmark instances. Besides, the approach is robust as it obtains small deviations from the best-achieved solutions when executing multiple independent runs. We also consider the performance of our BRKGA on a new set of challenging large instances with up to 2851 vertices.