Optimal Vertex Cover for the Small-World Hanoi Networks

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 (9)

• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• 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
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Anomalous Diffusion on the Hanoi Networks
• Quantum Transport through Hierarchical Structures
• Geometry and Dynamics for Hierarchical Regular Networks