Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm

We study the Ising spin glass on random graphs with fixed connectivity z and with a Gaussian distribution of the couplings, with mean μ and unit variance. We compute exact ground states by using a sophisticated branch-and-cut method for z=4,6 and system sizes up to 1280 spins, for different values of μ. We locate the spin-glass/ferromagnet phase transition at μ=0.77±0.02(z=4) and μ=0.56±0.02(z=6). We also compute the energy and magnetization in the Bethe-Peierls approximation with a stochastic method, and estimate the magnitude of replica symmetry breaking corrections. Near the phase transition, we observe a sharp change of the median running time of our implementation of the algorithm, consistent with a change from a polynomial dependence on the system size, deep in the ferromagnetic phase, to slower than polynomial in the spin-glass phase.