  The minimum dominating set problem has wide applications in network science
and related fields. It consists of assembling a node set of global minimum size
such that any node of the network is either in this set or is adjacent to at
least one node of this set. Although this is a difficult optimization problem
in general, we show it can be exactly solved by a generalized leaf-removal
process if the network contains no core. If the network has an extensive core,
we estimate the size of minimum dominating sets by a mean-field theory and
implement a belief-propagation algorithm to obtain near-optimal solutions. Our
algorithms also perform well on real-world network instances.
