Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T00:41:21.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs

Part of: Algorithms - Computer Science Equilibrium statistical mechanics Theory of computing Markov processes

Published online by Cambridge University Press:  12 April 2021

Martin Dyer ,
Marc Heinrich ,
Mark Jerrum  and
Haiko Müller
Martin Dyer
Affiliation:
School of Computing, University of Leeds, Leeds LS2 9JT, UK
Marc Heinrich
Affiliation:
School of Computing, University of Leeds, Leeds LS2 9JT, UK
Mark Jerrum*
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK
Haiko Müller
Affiliation:
School of Computing, University of Leeds, Leeds LS2 9JT, UK
*
*Corressponding author. Email: m.jerrum@qmul.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the ‘winding’ technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514–527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.

MSC classification

Primary: 68Q25: Analysis of algorithms and problem complexity
Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68W20: Randomized algorithms 68W25: Approximation algorithms 82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 6 , November 2021 , pp. 905 - 921
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

†

All authors are supported by EPSRC grants EP/S016562/1 and EP/S016694/1, ‘Sampling in hereditary classes’.

References

Arbib, C. (1988) A polynomial characterization of some graph partitioning problems. Inform. Process. Lett. 26(5) 223–230.CrossRefGoogle Scholar
Bencs, F., Csikvári, P. and Regts, G. (2020) Some applications of Wagner’s weighted subgraph counting polynomial. arXiv:2012.00806.Google Scholar
Bodlaender, H. L. and Jansen, K. (2000) On the complexity of the maximum cut problem. Nordic J. Comput. 7(1) 14–31.Google Scholar
Cai, J.-Y. and Chen, X. (2017) Complexity Dichotomies for Counting Problems. Vol. 1: Boolean Domain. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Cai, J.-Y., Huang, S. and Lu, P. (2012) From Holant to #CSP and back: dichotomy for Holantc problems. Algorithmica 64(3) 511–533.CrossRefGoogle Scholar
Chen, Z., Liu, K. and Vigoda, E. (2020) Rapid mixing of Glauber dynamics up to uniqueness via contraction. CoRR, abs/2004.09083.Google Scholar
Fisher, M. E. (1966) On the dimer solution of planar Ising models. J. Math. Phys. 7(10) 1776–1781.CrossRefGoogle Scholar
Friedli, S. and Velenik, Y. (2018) Statistical Mechanics of Lattice Systems. Cambridge University Press, Cambridge. A concrete mathematical introduction.Google Scholar
Garey, M. R., Johnson, D. S. and Stockmeyer, L. (1976) Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3) 237–267.CrossRefGoogle Scholar
Goldberg, L. A., Martin, R. and Paterson, M. (2004) Random sampling of 3-colorings in ℤ. Random Struct. Algorithms 24(3) 279–302.CrossRefGoogle Scholar
Guruswami, V. (1999) Maximum cut on line and total graphs. Discrete Appl. Math. 92(2-3) 217–221.CrossRefGoogle Scholar
Huang, L., Lu, P. and Zhang, C. (2016) Canonical paths for MCMC: from art to science. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016, (R. Krauthgamer, ed), SIAM, pp. 514–527.CrossRefGoogle Scholar
Jerrum, M. (2003) Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2003.CrossRefGoogle Scholar
Jerrum, M. and Sinclair, A. (1993) Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22(5) 1087–1116.CrossRefGoogle Scholar
Jurčišinová, E. and Jurčišin, M. (2020) Ground states, residual entropies, and specific heat capacity properties of frustrated Ising system on pyrochlore lattice in effective field theory cluster approximations. Phys. A 554 124671.CrossRefGoogle Scholar
Kasteleyn, P. W. (1963) Dimer statistics and phase transitions. J. Mathematical Phys. 4 287–293.CrossRefGoogle Scholar
Kowalczyk, M. and Cai, J.-Y. (2016) Holant problems for 3-regular graphs with complex edge functions. Theory Comput. Syst. 59(1) 133–158.CrossRefGoogle Scholar
Luby, M. and Vigoda, E. (1999) Fast convergence of the Glauber dynamics for sampling independent sets. Random Struct. Algorithms 15(3–4) 229–241. Statistical Physics Methods in Discrete Probability, Combinatorics, and Theoretical Computer Science. Princeton, NJ, 1997.3.0.CO;2-X>CrossRefGoogle Scholar
McQuillan, C. (2013) Approximating Holant problems by winding. CoRR, abs/1301.2880.Google Scholar
Motwani, R. and Raghavan, P. (1995) Randomized algorithms. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Sinclair, A. (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1(4) 351–370.CrossRefGoogle Scholar
Syôzi, I. (1951) Statistics of Kagomé lattice. Progr. Theoret. Phys. 6 306–308.CrossRefGoogle Scholar
Štefankovič, D., Vempala, S. and Vigoda, E. (2009) Adaptive simulated annealing: a near-optimal connection between sampling and counting. J. ACM 56(3) Art. 18, 36.CrossRefGoogle Scholar
Wainwright, M. J. and Jordan, M. I. (2008) Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1(1-2) 1–305.CrossRefGoogle Scholar