Optimal Vertex Cover for the Small-World Hanoi Networks
arXiv:1103.5940 · doi:10.1103/PhysRevE.84.011108
Abstract
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 non-trivial 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.
RevTex, 24 pages; many corrections in text and figures; final version; for related information, see http://www.physics.emory.edu/faculty/boettcher/
References in corpus (24)
- Emergence of scaling in random networks
- The structure and function of complex networks
- Spatial Networks
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Ferromagnetic Phase Transition in Barabasi-Albert Networks
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
- Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Computational complexity arising from degree correlations in networks
- Small-World Bonds and Patchy Percolation on the Hanoi Network
- Hierarchical, Regular Small-World Networks
- Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
- Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
- Spin Domains Generate Hierarchical Ground State Structure in J=+/-1 Spin Glasses
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Anomalous Diffusion on the Hanoi Networks
- Fixed Point Properties of the Ising Ferromagnet on the Hanoi Networks
- A new method for analyzing ground-state landscapes: ballistic search
- Quantum Transport through Hierarchical Structures
- Geometry and Dynamics for Hierarchical Regular Networks
- Numerical Solution-Space Analysis of Satisfiability Problems
- How to evaluate ground-state landscapes of disordered systems thermodynamical correctly