Solving the Maximum Clique Problem using a Hybrid Particle Swarm Optimization Algorithm

This article tackles the maximum clique problem MCP known as an NP-hard graph problem. The maximum clique problem consists in finding in an undirected graph a complete sub-graph (clique) of maximum cardinality. As the MCP is a classical graph problem extensively studied, the main contribution of this paper is to use for the first time particle swarm to solve it. A hybrid particle swarm optimization algorithm HPSOD is proposed. First a PSO algorithm is designed, based on a sub-graph extraction approach named circular-arc graph CAG, then a local search heuristic is integrated to enhance its performance. Experimental tests carried out on DIMACS benchmarks show a globally good performance of the proposed algorithm and that it outperforms many existent approaches.