Subgraph extraction and metaheuristics for the maximum clique problem

The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of an order of all the vertices whereby those belonging to a maximum clique stay close enough to each other. Such an order can be identified via the extraction of a particular subgraph from the original graph. The problem can consequently be seen as a permutation problem that can be addressed efficiently by metaheuristics. We first design a memetic algorithm (MA) for this purpose. Computational experiments conducted on the DIMACS benchmark instances clearly show that our MA not only outperforms existing genetic approaches, but it also compares very well to state‐of‐the‐art algorithms regarding the maximal clique size found after different runs. Furthermore, we show that a hybridization of MA with an iterated local search (ILS) improves the stability of the algorithm. This hybridization (MA‐ILS) permits to find two distinct maximal cliques of size 79 and one of size 80 for the C2000.9 instance of the DIMACS benchmark.