Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics

Abstract

The minimal dominating Set (MDS) problem is a prototypical hard combinatorial optimization problem. Two years ago we studied this problem by cavity method. Although we get the solution of a given graph, which gives very good estimation of minimal dominating size, but we don't know whether we get the ground state solution and how many solutions exist in the ground state. For this purpose, last year we continue to develop the one step replica symmetry breaking (RSB) theory to find the ground state energy of the MDS problem. Finally we find that 1) The MDS problem solution space has both condensation transition and cluster transition on regular Random (RR) graph and we prove this by simulated annealing dynamical process. 2) We developed zero temperature Survey Propagation (SP) algorithm on ER graph to estimate the ground state energy and to get Survey Propagation Decimation (SPD) algorithm with good results same as BPD algorithm.

16pages,6figures,2tables

References in corpus (24)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The Entropy of the K-Satisfiability Problem
• Reconstruction on trees and spin glass transition
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• A ferromagnet with a glass transition
• Simplest random K-satisfiability problem
• Exact solutions for diluted spin glasses and optimization problems
• Spin glass approach to the feedback vertex set problem
• Minimum Dominating Sets in Scale-Free Network Ensembles
• Network Observability Transitions
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Distance-d covering problems in scale-free networks with degree correlations
• Statistical Mechanics of the Minimum Dominating Set Problem
• Statistical mechanics of the vertex-cover problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Suppressing epidemics on networks by exploiting observer nodes
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT
• Feedback arcs and node hierarchy in directed networks

Cited by in corpus (4)

• Two faces of greedy leaf removal procedure on graphs
• Two-distance minimal dominating set problem studied by statistical mechanics and simulated annealing
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics
• Statistical Mechanics of the L-Distance Minimal Dominating Set problem