Large Cliques Elude the Metropolis Process

作者：Mark Jerrum · 发表于：Random Structures and Algorithms · 年份：1992 · DOI：10.1002/rsa.3240030402 · 被引用次数：329 · 研究领域：Advanced Graph Theory Research、Complexity and Algorithms in Graphs、Computational Geometry and Mesh Generation

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.