Revisiting the Challenges of MaxClique

Raffaele Marino, Scott Kirkpatrick

The MaxClique problem, finding the largest complete subgraph in an Erd{ö}s-R{é}nyi $G(N,p)$ random graph in the large $N$ limit, is a well-known example of a simple problem for whi…