Reactive and dynamic local search for Max-Clique, does the complexity pay off?

This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Maximum Clique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.