Grandes cliques eluden el proceso Metropolis

Resumen En un grafo aleatorio con n vértices, la clic máxima es probable que sea de un tamaño muy cercano a 2 lg n. Sin embargo, la clic producida al aplicar la ingenua heurística "greedy" a un grafo aleatorio es poco probable que tenga un tamaño mucho mayor que lg n. El factor de dos que separa estas estimaciones motiva la búsqueda de heurísticas más efectivas. Este artículo analiza una estrategia de búsqueda heurística, el proceso Metropolis, que es solo un paso por encima de la heurística greedy en su nivel de sofisticación. Se demuestra que el proceso Metropolis toma un tiempo super-polinómico para localizar una clic que es solo ligeramente más grande que la producida por la heurística greedy.