Premium
Large Cliques Elude the Metropolis Process
Author(s) -
Jerrum Mark
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030402
Subject(s) - heuristics , clique , heuristic , combinatorics , greedy algorithm , random graph , graph , clique problem , mathematics , computer science , mathematical optimization , theoretical computer science , chordal graph , 1 planar graph
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.