Phase transition in the maximum clique problem: the case of Erdos-Renyi graphs

Kazuhito Shida

A phase transition, like the one already found on Boolean satisfiability problem by Kirkpatrick and Selman, is found on max clique problem on ER graphs. Although number of the data…