Hard instances for the maximum clique problem

Abstract

A clique in a graph is a set of vertices in which all of its elements are pairwise adjacent. The Maximum Clique problem is a classic optimization problem in Graph Theory in which the objective is to find a maximum clique in a input graph G. Despite the existence of several theoretical hardness results for this problem, several experiments paint it as easier than one would expect. In this work, we approach a class of Branch and Bound algorithms for this problem, and how they make Maximum Clique often easier in practice. Furthermore, we analyze the correlation between cliques and colorings and the hardness difference in enumerating these structures. Besides that, we present instances whose solution via enumeration is more complex when compared to the average. Finally, we analyze a family of worst case instances for a more specific class of algorithms and propose a pre-processing that makes it possible for these instances to be solved in polynomial time, as well as a randomized construction that builds instances that are immune to this pre-processing.