A short review on the maximum clique problem algorithms with classical, AI, and quantum methods

Abstract

This manuscript provides a comprehensive review of the Maximum Clique Problem, a computational problem that involves finding subsets of vertices in a graph that are all pairwise adjacent to each other. As such, this review is a continuation of the series of previous reviews from 1994, 1999 and 2014. The manuscript covers in a simple way classical algorithms and includes a review of recent developments in graph neural networks and quantum algorithms.

41 pages

References in corpus (45)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Parallel Tempering Algorithm for Conformational Studies of Biological Molecules
• Social Structure of Facebook Networks
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Rydberg atom quantum technologies
• Efficient learning of quantum noise
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Quantum Annealing Correction with Minor Embedding
• Finding One Community in a Sparse Graph
• Graph Convolutional Neural Networks via Scattering
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Solving large Maximum Clique problems on a quantum annealer
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Algorithms for the minimum sum coloring problem: a review
• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
• Generalized Belief Propagation Algorithms for Decoding of Surface Codes
• Shuttling of Rydberg ions for fast entangling operations
• On the Power of Simple Reductions for the Maximum Independent Set Problem
• A Unifying View of Explicit and Implicit Feature Maps of Graph Kernels
• Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes
• Hard Optimization Problems have Soft Edges
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Parallel Tempering for the planted clique problem
• Solving the Maximum Clique Problem with Symmetric Rank-One Nonnegative Matrix Approximation
• Revisiting the Challenges of MaxClique
• Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
• Criticality and conformality in the random dimer model
• Belief propagation on networks with cliques and chordless cycles
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• Phase transition in compressed sensing with horseshoe prior
• Quantum computing and the stable set problem
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems
• Robust Quantum Circuit for Clique Problem with Intermediate Qudits