The Multilevel Splitting algorithm for graph colouring with application to the Potts model

Abstract

Calculating the partition function of the zero-temperature antiferromagnetic model is an important problem in statistical physics. However, an exact calculation is hard since it is strongly connected to a fundamental combinatorial problem of counting proper vertex colourings in undirected graphs, for which an efficient algorithm is not known to exist. Thus, one has to rely on approximation techniques. In this paper, we formulate the problem of the partition function approximation in terms of rare-event probability estimation and investigate the performance of a particle-based algorithm, called Multilevel Splitting, for handling this setting. The proposed method enjoys a provable probabilistic performance guarantee and our numerical study indicates that this algorithm is capable of delivering accurate results using a relatively modest amount of computational resources.

Keywords:

• Partition function
• graph colouring
• Multilevel Splitting
• rare events

Acknowledgements

We are thoroughly grateful to the anonymous reviewers for their valuable and constructive remarks and suggestions.

Notes

No potential conflict of interest was reported by the authors.

1 http://mat.gsia.cmu.edu/COLOR/instances.html.

Additional information

Funding

This work was supported by the Australian Research Council Centre of Excellence for Mathematical & Statistical Frontiers [grant number CE140100049]. We would also like to thank Robert Salomone, for fruitful discussions at the early stage of this work.