Statistical Mechanics of the Minimum Dominating Set Problem

The minimum dominating set (MDS) problem [1] has fundamental importance in network science. For example, to ensure the proper functioning of a complex networked system such as a nation-wide power grid, it is often necessary to monitor the system’s microscopic dynamics in real-time by placing sensors on the nodes. A sensor may have the capability of observing the instantaneous states of the residing node and all its adjacent nodes in the network [2], so they may not need to occupy all the nodes. We then have the MDS problem: How to place sensors on as few nodes as possible to minimize costs but still ensure that each node is either occupied or adjacent to at least one occupied node? As an example we show in Fig. 1b a minimum dominating set (containing only three nodes) of a small network. A more stringent constraint, which is adopted in lattice glass models [3], is to require an empty node $i$ to be surrounded by at least $l_i$ occupied nodes, with $l_i$ being node-dependent. The MDS problem corresponds to the case of $l_i \equiv 1$, while the other limiting case of $l_i = d_i$ is just the vertex cover (or independent set) problem [4, 5], where $d_i$ is node $i$’s degree (i.e., number of adjacent nodes).

The MDS problem has wide practical applications, such as monitoring large-scale power grids and other transportation systems [2], controlling the spreading of infectious diseases and other network dynamical processes [6–9], efficient routing in wireless networks [10], and network public goods games (e.g., resource allocation) [11]. Another application is to build a coarse-grained representation for a complex network starting from a MDS. Such an idea has already been applied to multi-document summarization in the field of information extraction [12]. Each node $i$ of the MDS can be regarded as a representative node for a local domain of the network. We can take the subnetwork induced by node $i$ and all its adjacent nodes (except those in the MDS) as a coarse-grained node, and set up an coarse-grained link between two coarse-grained nodes if the two corresponding subnetworks share at least one node or are connected by at least one link in the original network (see Fig. 1c for an example). If such a coarse-graining process is iterated we will then obtain a hierarchical representation for the original network, which may be very useful for understanding the organization of a complex system and for searching and information transmission in such a system.

Exactly solving the MDS problem, however, is extremely difficult in general, since it is a nondeterministic polynomial-complete (NP-complete) optimization problem [1]. Even the task of approximately solving the MDS problem is very hard. For a general network of $N$ nodes, so far the best polynomial algorithms can only guarantee to get dominating sets with sizes not exceeding $\ln N$ times of the minimum size [13, 14]. Many local-search algorithms have been proposed to solve the MDS problem heuristically (see review [1] and [2, 6, 7, 9, 15, 16]), but theoretical results on the MDS sizes of random network ensembles are still very rare.

In this work we bring several new theoretical and algorithmic contributions. We show in Sect. 2 that a generalized leaf-removal (GLR) process may cause a core percolation transition, and propose a quantitative theory to describe this percolation. If the network contains no core, GLR reaches an exact MDS; if an extensive core exists, we combine GLR with a local greedy process in Sect. 3 to get an upper bound to the MDS size. We then introduce a spin glass model in Sect. 4 and estimate the MDS size by a replica-symmetric (RS) mean field theory, and implement a message-passing algorithm in Sect. 5 to get near-optimal dominating sets for single random network instances. Our algorithms also perform well on real-world network instances. This work shall be useful both for network scientists who are interested in applying the MDS concept to practical problems, and for applied mathematicians who seek better theoretical understanding on the random MDS problem.

Consider a simple network $W$ formed by $N$ nodes and $M$ undirected links, each link connecting between two different nodes. Each node with index $i\in \{1, 2, \ldots , N\}$ is either empty (indicated by the occupation state $c_i=0$) or occupied by sensors ($c_i=1$). A node $i$ is regarded as observed if it is occupied or it is empty but adjacent to one or more occupied nodes, otherwise it is regarded as unobserved. We need to occupy a set $\Gamma$ of nodes to make all the $N$ nodes be observed, and the objective is to make the dominating set $\Gamma$ as small as possible, i.e., to construct a minimum dominating set. It is easy to verify that the three occupied nodes of Fig. 1b form a MDS for that small network. Notice a network may have more than one MDS.

2.1 The GLR Process

Here we extend the leaf-removal idea of [17] (see also more recent work [6, 18, 19]) and consider a generalized leaf-removal process. This dynamics is based on the following two considerations: first, as pointed out in [6, 17], if node $i$ is an unobserved leaf node (which has only a single neighbor, say $j$), then occupying $j$ but leaving $i$ empty must be an optimal strategy; second, we notice that if $i$ is an empty but observed node and at most one of its adjacent nodes is unobserved, then it must be an optimal strategy not to occupy $i$. This second point was not considered in the conventional leaf-removal process [6].

The GLR process simplifies the input network $W$ at discrete evolution steps $t=0, 1, 2, \ldots$. For the convenience of description, let us denote by $W_t$ the simplified network at the start of the $t$-th evolution step of GLR. $W_0$ at the initial step $t=0$ is identical to the original network $W$, and all the nodes of $W_0$ are unobserved. We prove that if GLR makes the whole input network $W$ be observed, then the set of nodes occupied during this process must be a MDS. For this latter purpose, let us denote by $\Gamma _0$ a MDS of the input network $W$ (there must be at least one such set). The essential idea is to demonstrate that during GLR, we can modify $\Gamma _{0}$ in such a way that its size does not change but all the nodes $i$ that are fixed to be occupied ($c_i=1$) are in $\Gamma _{0}$ while all the nodes $j$ that are fixed to be unoccupied ($c_j=0$) are not in $\Gamma _{0}$. Starting from evolution step $t=0$, let us perform GLR and modify $\Gamma _{0}$ in the following sequential order:

1. (0)

   As long as there is an isolated node $i$ in network $W_t$, fix its occupation state to $c_i=1$ and delete it from $W_t$. All such fixed nodes $i$ must also belong to $\Gamma _{0}$.

    
2. (1)

   As long as there is a leaf node $i$ in network $W_t$ which is not yet observed, fix the occupation state of its unique neighbor $j$ to $c_j=1$ and fix that of $i$ to $c_i=0$ so that $j$ and all its adjacent nodes (including $i$) are now observed, see Fig. 2 (left panel). We then delete node $j$ and all its connected links from $W_t$. If $j$ belongs to $\Gamma _{0}$ then node $i$ must not belong to it, because otherwise $\Gamma _{0}$ could not have been a MDS. On the other hand, if node $j$ does not belong to $\Gamma _{0}$ then node $i$ must belong to it, and in this latter case we modify $\Gamma _{0}$ by adding $j$ to it and deleting $i$ from it.

    
3. (2)

   Then as long as there is a node $i$ which is itself observed and which has only a single unobserved neighbor $j$, delete the link $(i,j)$ from network $W_t$, see Fig. 2 (right panel). We do not modify $\Gamma _{0}$ if node $i$ does not belong to it. If node $i$ does belong to $\Gamma _{0}$ then node $j$ must not belong to it, and in this latter case we add $j$ to $\Gamma _{0}$ and delete $i$ from it.

    
4. (3)

   Then as long as there is an observed node $i$ which is not connected to any unobserved node, fix its occupation state to $c_i=0$ and delete it and all its attached links from $W_t$. Such a node $i$ must not belong to $\Gamma _{0}$, for otherwise $\Gamma _{0}$ could not have been a MDS.

    
5. (4)

   If the resulting network $W_t$ is empty or it contains no isolated node nor leaf node, the GLR process stops. If $W_t$ still contains at least one isolated or leaf node, then we increase the evolution step from $t$ to $(t+1)$ and initialize the network $W_{t+1}$ as identical to $W_t$. A node $i$ of $W_{t+1}$ is regarded as observed if and only if it is observed in network $W_t$. We then repeat the above-mentioned operations (1)–(3).

    

If the final simplified network is non-empty, then there must be some nodes that are still unobserved after the GLR process. The subnetwork induced by these unobserved nodes is referred to as the core of the original network $W$. This core is connected only to observed empty nodes but not to occupied nodes. We denote by $n_{core}$ the fraction of nodes in this core and by $w$ the fraction of occupied nodes.

If the original network $W$ has no core, then the set $\Gamma$ of occupied nodes by the GLR process must be identical to the final $\Gamma _{0}$, which is a MDS modified from the original MDS. We have therefore proven that GLR constructs a MDS for a network $W$ if this network contains no core. (All the above-mentioned modification operations on $\Gamma _0$ are ignored in the actual implementation of the GLR process. They are introduced here solely for proving that GLR is able to construct a MDS if there is no core.) Furthermore, we notice that if the GLR process finishes with some nodes remaining to be unobserved, the set of nodes occupied during this process must be a MDS for the subnetwork of $W$ induced by all the observed nodes. This is because all these occupied nodes also belong to the modified MDS $\Gamma _{0}$, while all those nodes fixed to be unoccupied are outside of $\Gamma _{0}$.

We generate many large instances of Erdös–Rényi (ER) and scale-free (SF) random networks and run the GLR process on them (details of the network sampling method are given in Sects. 2.3, 2.4, and 2.5). Some representative results are shown in Fig. 3 for ER networks [20, 21], in Fig. 4 for SF networks generated through the static model [22], and in Fig. 5 for pure SF networks [20, 21]. A major observation is that there is no core in pure SF random networks with minimum node degree $d_{min}=1$, therefore a MDS for such a network can be easily constructed by the GLR process. Another major observation is that there is a continuous core percolation transition in ER networks and in SF networks generated through the static model. This core percolation transition occurs at certain threshold value of the mean node degree. For example, for ER networks with $N=10^6$ nodes and $M= (c/2) N$ links, when the mean node degree $c<2.41$ there is no core ($n_{core}=0$), and GLR reaches a MDS for the whole network (Fig. 3). The core emerges at $c\approx 2.41$ and its relative size $n_{core}$ then increases with $c$ continuously from zero. For $c>2.41$, GLR constructs a MDS only for part of the ER network and it leaves an extensive core of $n_{core} N$ unobserved nodes.

Notice the core percolation transition resulting from the GLR optimization process is qualitatively different from the simpler observability transition discussed in [2], which considers the appearance of a giant connected component of observed nodes resulting from an initial set of randomly chosen occupied nodes. We now develop a percolation theory to thoroughly understand the GLR dynamics on random networks.

2.4 Results on Scale-Free Random Networks Generated Through the Static Model

Now let us consider GLR-induced core percolation on more heterogeneous random networks. We generate a scale-free network $W$ of $N$ nodes and $M=(c/2) N$ links according to the static model [22]. Each node $i \in \{1, 2, \ldots , N\}$ is first assigned a fitness value $\theta _i = i^{-\xi }/(\sum _{j=1}^{N} j^{-\xi })$, where $0 \le \xi < 1$ is a control parameter. Then we add links between pairs of these $N$ nodes in a sequential manner. To create a link, two nodes $i$ and $j$ are chosen independently from the set of $N$ nodes, and the probability that $i$ and $j$ being chosen is equal to $\theta _i \theta _j$; if nodes $i$ and $j$ are different and the link $(i, j)$ has not been created before, this link is added to network. The final network $W$ has a power-law degree distribution $P(d) \propto d^{-\lambda }$ for $d \gg 1$, with degree decay exponent $\lambda = 1 + 1/ \xi$. In the thermodynamic limit $N\rightarrow \infty$, an explicit expression for $P(d)$ is obtained as [26]

$$\begin{aligned} P(d)=\frac{[c (1-\xi )]^d}{d! \xi }\int _{1}^{\infty } \mathrm{d} x e^{-c (1-\xi ) x} x^{k-1-1/\xi }\quad \quad \quad \quad (d\ge 0). \end{aligned}$$

(21)

For $N=\infty$, a continuous core percolation phase transition is observed in such a SF network, and this transition occurs at more and more larger value of the mean node degree $c$ as the decay exponent $\lambda$ decreases (see Fig. 4 for $\lambda =3.5$, 3.0, $8/3\approx 2.667$, and 2.5 and Fig. 6 for $2< \lambda \le 6$). When the decay exponent $\lambda$ is less then 3.0, theoretical predictions obtained at $N=\infty$ are quantitatively different from theoretical and simulation results obtained on finite (e.g., $N=10^6$) network instances, with the deviations become more pronounced as $\lambda$ is closer to 2.0. Such a finite-size effect is mainly caused by the natural cutoff of maximum node degree in finite networks (it was also observed in our earlier work [23] on another type of percolation transitions). We emphasize that for a give finite value of $N$, the results of the core percolation theory agree with the simulation results of the actual GLR process very well, especially if we average the theoretical and simulation results over many network instances to reduce fluctuations.

For random SF networks generated through the static model with $N=\infty$ nodes, the core percolation transition value of mean node degree $c$ is very sensitive to the decay exponent $\lambda$ in the region of $2 < \lambda < 2.5$, and it diverges as $\lambda$ approaches 2.0 from above (Fig. 6). At the other limit of $\lambda \rightarrow \infty$, the mean node degree at the phase transition approaches the value of $c\approx 2.4102$, which is just the core percolation phase transition point of an infinite ER random network.

There is a very simple greedy algorithm in the literature to solve the MDS problem approximately, which is based on the concept of node impact [1, 7, 16]). The impact of an unoccupied node $i$ equals to the number of nodes that will be observed by occupying $i$. For example, if node $i$ has 3 unobserved neighbors, its impact is 4 if $i$ is itself unobserved and is 3 if $i$ is already adjacent to one or more occupied nodes. Starting from an input network $W$ with all the nodes unobserved, the greedy algorithm selects uniformly at random a node $i$ from the subset of nodes with the highest impact and fix its occupation state to $c_i=1$. All the adjacent nodes of $i$ are then observed. If there are still unobserved nodes in the network, the impact value for each of the unoccupied nodes is updated and the greedy occupying process is repeated until all the nodes are observed. This pure greedy algorithm is very easy to implement and very fast, but we find that it usually fails to reach a true MDS even when the input network contains no core.

Here we introduce an improved local algorithm by combining the GLR process with the impact-based greedy process. We call this new algorithm the GLR-Impact hybrid algorithm. Given an input network $W$ with all the nodes unobserved, we first carry out the GLR process to simplify $W$ as far as possible. If all the nodes are observed during this initial GLR process, a MDS of network $W$ is then constructed. For the nontrivial case of some nodes being left unobserved after this GLR process, we first occupy a randomly chosen node from the subset of highest-impact nodes and then perform the GLR process again to further simplify the network as far as possible. We keep repeating such a occupying-followed-by-GLR process until there is no unobserved node left in the network.

The GLR-Impact hybrid algorithm is also very easy to implement and very fast. Its performance is demonstrated in Fig. 7 for single ER networks and regular random (RR) networks. (All the nodes of a RR network have the same integer degree $c$ but the network is otherwise completely random [23]). This hybrid local algorithm outperforms the pure greedy algorithm considerably for $c \le 10$, but it is still inferior to the belief-propagation-guided decimation (BPD) algorithm of Sect. 5.

We also test the performance of the hybrid algorithm on single SF random networks generated through the static model [22] (see Fig. 8). The GLR-Impact algorithm still outperforms the pure greedy algorithm on these heterogeneous networks, and its performance approaches that of the BPD algorithm as the network becomes more and more heterogeneous (i.e., as the decay exponent $\lambda$ approaches 2.0 from above).

Real-world networks are often very heterogenous, with a small fraction of highly connected nodes [21]. As a test of the algorithms introduced in this work, we apply the GLR process, the pure greedy algorithm, the hybrid algorithm, and the BPD algorithm to a set of twelve real-world networks. Among these network instances, five are infrastructure networks: European express road network (RoadEU [28]), road network of Texas (RoadTX [29]), power grid of western US states (Grid [30]), and two Internet networks at the autonomous systems level (IntNet1 and IntNet2 [31]); three are information networks: Google webpage network (WebPage [29]), European email network (Email [32]), and research citation network (Citation [31]); three are social contact networks: collaboration network of condensed-matter authors (Author [32]), peer-to-peer interaction network (P2P [33]),and on-line friendship network (Friend [34]); the remaining one is the biological network of protein-protein interactions (PPI [35]).

For a given network $W$, the RS mean field theory gives an estimate for the occupation probability $q_{i}^{+1}$ of each node $i$, see Eq. (24). Such information is exploited in a BPD algorithm to construct a near-optimal dominating set. (Such an algorithm and its extensions have already been successfully applied to many other combinatorial optimization problems, e.g., the $K$-satisfiability problem [39, 40] and the vertex-cover problem [5]). At each round of the BPD process, unoccupied nodes with the highest estimated occupation probabilities are added to the dominating set, and the occupation probabilities for the remaining unoccupied nodes are then updated.

The results of the BPD algorithm for random networks and for real-world networks are compared with the results obtained by the local heuristic algorithms in Figs. 7,  8, and Table 1. For ER and RR random networks, the BPD algorithm considerably beats both the pure greedy algorithm and the GLR-Impact hybrid algorithm; for very heterogeneous (e.g., scale-free) networks, the BPD algorithm only slightly outperforms the GLR-Impact algorithm.

In this work, we proposed two heuristic algorithms (a GLR-Impact local algorithm and a BPD message-passing algorithm) and presented a core percolation theory and a replica-symmetric mean field theory for solving the network dominating set problem algorithmically and theoretically. We found that the GLR process may lead to a core percolation transition in the network (see Figs. 3 and  4). Our numerical results shown in Figs. 7,  8 and Table 1 suggested that the GLR-Impact algorithm and the BPD algorithm can construct near-optimal dominating sets for random networks and real-world networks.

There are many theoretical issues remaining to be investigated. An easy extension of the core percolation theory is to consider GLR with a subset of initially occupied nodes. By optimizing this initial subset (e.g., following the methods of [41–43]), we may reach an improved lower-bound to the MDS size. Core percolation on degree-correlated random networks [44] and in the more general lattice glass problem [3] are also very interesting. When the random network has an extensive core, we observed that the belief-propagation Eq. (25) fails to converge at large values of the re-weighting parameter $x$ (see Fig. 9), indicating a spin glass phase transition. A systematic study of the spin glass phase will be carried out using the first-step replica-symmetry-breaking mean field theory [40, 45, 46], which may in addition offer an improved estimate on the ensemble-averaged MDS size. The possible deep connections between core percolation and the complexity of the random MDS problem will also be addressed by adapting the long-range frustration theory [24, 25].

The methods of this work can be readily extended to the MDS problem of directed networks. Our theoretical and algorithmic results on the directed MDS problem will soon be reported in an accompanying paper [47]. A more challenging problem is the connected dominating set problem [48] which has the additional constraint that the nodes in the dominating set should induce a connected subnetwork. Our present work may stimulate further theoretical studies on this hard problem.