  A minimum dominating set for a digraph (directed graph) is a smallest set of
vertices such that each vertex either belongs to this set or has at least one
parent vertex in this set. We solve this hard combinatorial optimization
problem approximately by a local algorithm of generalized leaf removal and by a
message-passing algorithm of belief propagation. These algorithms can construct
near-optimal dominating sets or even exact minimum dominating sets for random
digraphs and also for real-world digraph instances. We further develop a core
percolation theory and a replica-symmetric spin glass theory for this problem.
Our algorithmic and theoretical results may facilitate applications of
dominating sets to various network problems involving directed interactions.
