On comparing algorithms for the maximum clique problem

Abstract Several algorithms for the exact solution of the maximum clique problem are available in the literature. Some have been proposed with the aim of bounding the worst case complexity of the problem, while others focus on practical performance as evaluated experimentally. These two groups of works are somewhat independent, in the sense that little experimental investigation is available in the former group, and little theoretical analysis exists for the latter. Moreover, the experimental results seem to be much better than could be expected from the theoretical results. We show that a broad class of branch and bound algorithms for the maximum clique problem display sub-exponential average running time behavior, and also show how this helps to explain the apparent discrepancy between the theoretical and experimental results. We also propose a more structured methodology for the experimental analysis of algorithms for the maximum clique problem, which takes into account the peculiarities of cliques in random graphs, bringing the theoretical and experimental approaches closer together in the search for better algorithms. As a proof of concept, we apply the proposed methodology to thirteen algorithms from the literature.