Spin Glass approach to the 2-Distance Minimal Dominating Set problem.

The L-Distance Minimal Dominating Set (LDMDS) problem is widely applied in the various kind of Dominating Set problems. Recently we studied Regular Dominating Set problem by cavity method, we develop two algorithms (Belief Propagation Decimation algorithm and Survey Propagation Decimation algorithm) to obtain the solution of a given graph, which gives very good estimation of minimal dominating size.This year we develop Spin Glass theory to study the 2-Distance MDS problem. Firstly we find that the entropy always is positive at any inverse temperature on the Erdos Renyi Random Graph, the transition point occur at the $\beta=\infty$. Secondly the entropy has the transition point at the finite inverse temperature on the Regular Random Graph when the node degree from 2 to 9, there is no entropy trnsition point (or $\beta=\infty$) in the other circumstance. Thirdly the results of the BP algorithm same with the Replica Symmetry theory and the results of the BPD algorithm better than the Greedy heuristic algorithm. \textbf{\large Keywords: }2-Distance Minimal Dominating Set, Belief Propagation, ER random graph, Regular Random graph, Belief Propagation Decimation.