A new method for analysing ground-state landscapes: ballistic search

Optimal vertex cover for the small-world Hanoi networks

The vertex-cover problem on the Hanoi networks HN3 and HN5 is analyzed with an exact renormalization group and parallel-tempering Monte Carlo simulations. The grand canonical partition function of the equivalent hard-core repulsive lattice-gas problem is recast first as an Ising-like canonical partition function, which allows for a closed set of renormalization-group equations. The flow of these equations is analyzed for the limit of infinite chemical potential, at which the vertex-cover problem is attained. The relevant fixed point and its neighborhood are analyzed and nontrivial results are obtained both for the coverage as well as for the ground-state entropy density, which indicates the complex structure of the solution space. Using special hierarchy-dependent operators in the renormalization group and Monte Carlo simulations, structural details of optimal configurations are revealed. These studies indicate that the optimal coverages (or packings) are not related by a simple symmetry. Using a clustering analysis of the solutions obtained in the Monte Carlo simulations, a complex solution space structure is revealed for each system size. Nevertheless, in the thermodynamic limit, the solution landscape is dominated by one huge set of very similar solutions.

Numerical solution-space analysis of satisfiability problems

The solution-space structure of the three-satisfiability problem (3-SAT) is studied as a function of the control parameter α (ratio of the number of clauses to the number of variables) using numerical simulations. For this purpose one has to sample the solution space with uniform weight. It is shown here that standard stochastic local-search (SLS) algorithms like average satisfiability (ASAT) exhibit a sampling bias, as does "Metropolis-coupled Markov chain Monte Carlo" (MCMCMC) (also known as "parallel tempering") when run for feasible times. Nevertheless, unbiased samples of solutions can be obtained using the "ballistic-networking approach," which is introduced here. It is a generalization of "ballistic search" methods and yields also a cluster structure of the solution space. As application, solutions of 3-SAT instances are generated using ASAT plus ballistic networking. The numerical results are compatible with a previous analytical prediction of a simple solution-space structure for small values of α and a transition to a clustered phase at α(c)≈3.86 , where the solution space breaks up into several non-negligible clusters. Furthermore, in the thermodynamic limit there are, even for α=4.25 close to the SAT-UNSAT transition α(s)≈4.267 , always clusters without any frozen variables. This may explain why some SLS algorithms are able to solve very large 3-SAT instances close to the SAT-UNSAT transition.

Clustering analysis of the ground-state structure of the vertex-cover problem

Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c<e , the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a branch-and-bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e . For small connectivities, the solutions are collected in a finite small number of clusters, while the number of clusters diverges slowly with system size for larger connectivities and replica symmetry breaking, but not one-step replica symmetry breaking (1-RSB) occurs.

Spin domains generate hierarchical ground state structure in J = +/-1 spin glasses

Unbiased samples of ground states were generated for the short-range Ising spin glass with J(ij) = +/-1, in three dimensions. Clustering the ground states revealed their hierarchical structure, which is explained by correlated spin domains, serving as cores for macroscopic zero energy "excitations."

Ground-state clusters of two-, three-, and four-dimensional +/-J Ising spin glasses

A huge number of independent true ground-state configurations is calculated for two-, three- and four-dimensional +/-J spin-glass models. Using the genetic cluster-exact approximation method, system sizes up to N=20(2),8(3),6(4) spins are treated. A "ballistic-search" algorithm is applied, which allows even for large system sizes to identify clusters of ground states that are connected by chains of zero-energy flips of spins. The number of clusters n(C) diverges with N going to infinity. For all dimensions considered here, an exponential increase of n(C) appears to be more likely than a growth with a power of N. The number of different ground states is found to grow clearly exponentially with N. A zero-temperature entropy per spin of s(0)=0.078(5)k(B) (2D), s(0)=0.051(3)k(B) (3D), respectively, s(0)=0.027(5)k(B) (4D) is obtained.