Approximate ground states of the random-field Potts model from graph cuts

Manoj Kumar, Ravinder Kumar, Martin Weigel, Varsha Banerjee, Wolfhard Janke, Sanjay Puri

    Research output: Contribution to journalArticlepeer-review

    7 Citations (Scopus)
    33 Downloads (Pure)


    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
    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 languageEnglish
    Article number053307
    Pages (from-to)1-10
    Number of pages10
    JournalPhysical review E: Statistical, Nonlinear, and Soft Matter Physics
    Issue number5
    Publication statusPublished - 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.


    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