A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
arXiv:2403.09742 · doi:10.1038/s42005-026-02606-7
summary
The paper surveys algorithms for solving the maximum clique problem, covering classical exact and heuristic methods as well as recent graph neural network and quantum computing approaches.
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
Topics & keywords
#maximum clique problem#graph algorithms#classical algorithms#graph neural networks#quantum computingbranch and boundexact algorithmsgraph neural networkquantum annealingNP-hard