Large Cliques Elude the Metropolis Process

Abstract In a random graph on n vertices, the maximum clique is likely to be of size very close to 2 lg n . However, the clique produced by applying the naive “greedy” heuristic to a random graph is unlikely to have size much exceeding lg n . The factor of two separating these estimates motivates the search for more effective heuristics. This article analyzes a heuristic search strategy, the Metropolis process , which is just one step above the greedy one in its level of sophistication. It is shown that the Metropolis process takes super‐polynomial time to locate a clique that is only slightly bigger than that produced by the greedy heuristic.