Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem

Alessio Troiani ()
Additional contact information
Alessio Troiani: Dipartimento di Matematica e Informatica, Università di Perugia, Via Vanvitelli, 06123 Perugia, Italy

Mathematics, 2024, vol. 12, issue 18, 1-16

Abstract: We consider the problem of finding the largest clique of a graph. This is an NP-hard problem and no exact algorithm to solve it exactly in polynomial time is known to exist. Several heuristic approaches have been proposed to find approximate solutions. Markov Chain Monte Carlo is one of these. In the context of Markov Chain Monte Carlo, we present a class of “parallel dynamics”, known as Probabilistic Cellular Automata, which can be used in place of the more standard choice of sequential “single spin flip” to sample from a probability distribution concentrated on the largest cliques of the graph. We perform a numerical comparison between the two classes of chains both in terms of the quality of the solution and in terms of computational time. We show that the parallel dynamics are considerably faster than the sequential ones while providing solutions of comparable quality.

Keywords: maximum clique problem; probabilistic cellular automata; Markov chain Monte Carlo; QUBO; parallel computing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/18/2850/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/18/2850/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:18:p:2850-:d:1477804

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().