Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics

作者：Habibulla, Yusupjan^*

来源：Journal of Statistical Mechanics: Theory and Experiment , 2017, 2017(10): 103402.

DOI：10.1088/1742-5468/aa8c1e

• cavity and replica method
• message-passing algorithms
• random graphs
• networks
• spin glasses

The minimal dominating set (MDS) problem is a prototypical hard combinatorial optimization problem. We recently studied this problem using the cavity method. Although we obtained a solution for a given graph that gives a very good estimation of the minimal dominating size, we do not know whether there is a ground state solution or how many solutions exist in the ground state. We have therefore continued to develop a one-step replica symmetry breaking theory to investigate the ground state energy of the MDS problem. First, we find that the solution space for the MDS problem exhibits both condensation transition and cluster transition on regular random graphs, and prove this using a simulated annealing dynamical process. Second, we develop a zero-temperature survey propagation algorithm on Erdos-Renyi random graphs to estimate the ground state energy, and obtain a survey propagation decimation algorithm that achieves results as good as the belief propagation decimation algorithm.

• 出版日期2017-10
• 单位新疆大学