Adaptive, restart, randomized greedy heuristics for maximum clique

This paper presents some adaptive restart randomized greedy heuristics for MAXIMUM CLIQUE. The algorithms are based on improvements and variations of previously-studied algorithms by the authors. Three kinds of adaptation are studied: adaptation of the initial state (AI) given to the greedy heuristi c, adaptation of vertex weights (AW) on the graph, and no adaptation (NA). Two kinds of initialization of the vertex-weights are investigated: unweigh ted initialization (w(i) := 1) and degree-based initialization (w(i) := d(i ) where d(i) is the degree of vertex i in the graph). Experiments are condu cted on several kinds of graphs (random, structured) with six combinations: {NA, AI, and AW} x {unweighted initialization, degree-based initialization }. A seventh state of the art semi-greedy algorithm, DMclique, is evaluated as a benchmark algorithm. We concentrate on the problem of finding large c liques in large, dense graphs in a relatively short amount of time. We find that the different strategies produce different effects, and that differen t algorithms work best on different kinds of graphs.