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 heuristic, adaptation of vertex weights (AW) on the graph, and no adaptation (NA). Two kinds of initialization of the vertex-weights are investigated: unweighted 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 conducted on several kinds of graphs (random, structured) with six combinations: {NA, AI, and AW} × {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 cliques in large, dense graphs in a relatively short amount of time. We find that the different strategies produce different effects, and that different algorithms work best on different kinds of graphs.