### Abstract

While the ground-state problem for the random-field Ising model is polynomial, and can be solved using a number of well-known algorithms for maximum flow or graph cut, the analog random-field Potts model corresponds to a multiterminal flow problem that is known to be NP-hard. Hence an efficient exact algorithm is very unlikely to exist. As we show here, it is nevertheless possible to use an embedding of binary degrees of freedom into the Potts spins in combination with graph-cut methods to solve the corresponding ground-state problem approximately in polynomial time. We benchmark this heuristic algorithm using a set of quasiexact ground states found for small systems from long parallel tempering runs. For a not-too-large number

q

of Potts states, the method based on graph cuts finds the same solutions in a fraction of the time. We employ the new technique to analyze the breakup length of the random-field Potts model in two dimensions.

q

of Potts states, the method based on graph cuts finds the same solutions in a fraction of the time. We employ the new technique to analyze the breakup length of the random-field Potts model in two dimensions.

Original language | English |
---|---|

Article number | 053307 |

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Physical review E: Statistical, Nonlinear, and Soft Matter Physics |

Volume | 97 |

Issue number | 5 |

DOIs | |

Publication status | Published - 14 May 2018 |

### Bibliographical note

Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.## Fingerprint Dive into the research topics of 'Approximate ground states of the random-field Potts model from graph cuts'. Together they form a unique fingerprint.

## Cite this

Kumar, M., Kumar, R., Weigel, M., Banerjee, V., Janke, W., & Puri, S. (2018). Approximate ground states of the random-field Potts model from graph cuts.

*Physical review E: Statistical, Nonlinear, and Soft Matter Physics*,*97*(5), 1-10. [053307]. https://doi.org/10.1103/PhysRevE.97.053307