  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.
