Revisiting the Challenges of MaxClique

Abstract

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 which finding any approximate solution within a factor of $2$ of the known, probabilistically determined limit, appears to require P$=$NP. This type of search has practical importance in very large graphs. Algorithmic approaches run into phase boundaries long before they reach the size of the largest likely solutions. And, most intriguing, there is an extensive literature of \textit{challenges} posed for concrete methods of finding maximum naturally occurring as well as artificially hidden cliques, with computational costs that are at most polynomial in the size of the problem. We use the probabilistic approach in a novel way to provide a more insightful test of constructive algorithms for this problem. We show that extensions of existing methods of greedy local search will be able to meet the \textit{challenges} for practical problems of size $N$ as large as $10^{10}$ and perhaps more. Experiments with spectral methods that treat a single large clique of size $\alpha N^{1/2}$ \textit{planted} in the graph as an impurity level in a tight binding energy band show that such a clique can be detected when $\alpha \ge \approx 1.0$. Belief propagation using a recent \textit{approximate message passing} (\textbf{AMP}) scheme of inference pushes this limit down to $\alpha \sim \sqrt{1/e}$. Exhaustive local search (with early stopping when the planted clique is found) does even better on problems of practical size, and proves to be the fastest solution method for this problem.

17 pages, 23 figures

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Parallel Tempering for the planted clique problem
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs

Cited by in corpus (4)

• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• Instantons in ${\varphi }^4$ Theories: Transseries, Virial Theorems and Numerical Aspects
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods