Abstract
While the groundstate problem for the randomfield Ising model is polynomial, and can be solved using a number of wellknown algorithms for maximum flow or graph cut, the analog randomfield Potts model corresponds to a multiterminal flow problem that is known to be NPhard. 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 graphcut methods to solve the corresponding groundstate 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 nottoolarge 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 randomfield 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 randomfield Potts model in two dimensions.
Original language  English 

Article number  053307 
Pages (fromto)  110 
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 noncommercial 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 randomfield Potts model from graph cuts'. Together they form a unique fingerprint.Profiles

Martin Weigel
Person