  The directed L-distance minimal dominating set (MDS) problem has wide
practical applications in the fields of computer science and communication
networks. Here, we study this problem from the perspective of purely
theoretical interest. We only give results for an Erd$\acute{o}$s
R$\acute{e}$nyi (ER) random graph and regular random graph, but this work can
be extended to any type of networks. We develop spin glass theory to study the
directed 2-distance MDS problem. First, we find that the belief propagation
algorithm does not converge when the inverse temperature exceeds a threshold on
either an ER random network or regular random network. Second, the entropy
density of replica symmetric theory has a transition point at a finite inverse
temperature on a regular random graph when the node degree exceeds 4 and on an
ER random graph when the node degree exceeds 6.6; there is no entropy
transition point (or $\beta=\infty$) in other circumstances. Third, the results
of the replica symmetry (RS) theory are in perfect agreement with those of
belief propagation (BP) algorithm while the results of the belief propagation
decimation (BPD) algorithm are better than those of the greedy heuristic
algorithm.
