Two-distance minimal dominating set problem studied by statistical mechanics and simulated annealing

Abstract

The L-distance (especially the 2-distance) minimal dominating set (MDS) problem is widely considered in various dominating set problems. Recently, we studied the regular dominating set problem using the cavity method and developed two algorithms (belief propagation decimation and survey propagation decimation) to estimate the solution of a given graph, resulting in very good estimations of the minimal dominating size. This paper describes the development of spin glass theory to study the 2-distance MDS problem. First, we show that the belief propagation equation does not converge when the inverse temperature $\beta$ is greater than a certain threshold value on both regular and Erdos--Renyi random networks. Second, we find that the entropy density is equal to zero at finite inverse temperature on regular random graphs when the node degree is from 3--9, and on Erdos--Renyi random networks when the node degree is from 4.2--10.4; the entropy density is positive in all other cases. This result is proved using a dynamical simulated annealing process. Third, the results of replica symmetry theory are shown to be in agreement with those of the belief propagation algorithm, and the results of the belief propagation decimation algorithm are found to be better than those of the greedy heuristic algorithm.

arXiv comment19pages, 6 figures

References in corpus (7)

• Spin glass approach to the feedback vertex set problem
• Statistical Mechanics of the Minimum Dominating Set 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
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT
• An Integer Linear Programming Formulation for the Convex Dominating Set Problems

Cited by in corpus (1)

• Statistical Mechanics of the L-Distance Minimal Dominating Set problem