1 Introduction↩︎

The minimum dominating set (MDS) problem is one of the classic and well-studied problems in graph algorithms, where given a graph \(G = (V,E)\), the goal is to find a set \(D \subseteq V\) of the smallest possible size so that every node is dominated by \(D\), i.e., either it is in \(D\) or has a neighbor in \(D\). In the centralized setting, the well-known greedy algorithm obtains \(\log(\Delta+1)\) approximation for graphs of maximum degree \(\Delta\) [1], which is optimal up to constant factors, as it is NP-Hard to achieve \(c \log \Delta\) approximation for some constant \(c\).

1.0.0.1 Distributed Model.

In the distributed setting, there is a communication network with \(n\) nodes that is identical to the input graph. Nodes communicate with each other in synchronous rounds, where the message size can be bounded by \(O(\log n)\) bits (known as \(\mathsf{CONGEST}\) model) or unbounded (known as \(\mathsf{LOCAL}\) model). Every node knows its neighbors in the beginning.

1.0.0.2 Distributed MDS on General Graphs.

In the distributed setting, the first efficient algorithm for MDS was introduced by Jia, Rajaraman, and Suel [2] who gave a randomized \(O(\log \Delta)\) expected approximation in \(O(\log n \log (\Delta+1))\) rounds w.h.p. in the \(\mathsf{CONGEST}\) model. Kuhn and Wattenhofer [3] gave a \(O(k\Delta^{2/k}\log \Delta)\) expected approximation in \(O(k^2)\) rounds for any arbitrary \(k\) in the \(\mathsf{CONGEST}\) model. This is the first non-trivial approximation in a constant number of rounds when \(k = O(1)\). Later, Kuhn, Moscibroda, and Wattenhofer [4] gave a randomized \((1+\varepsilon)(1 + \ln(\Delta+1))\) approximation in \(O(\varepsilon^{-4}\log^2\Delta)\) and \(O(\varepsilon^{-2}\log n)\) rounds in the \(\mathsf{CONGEST}\) and the \(\mathsf{LOCAL}\) model respectively.

In the deterministic world, Deurer, Kuhn, and Maus [5] provided two deterministic \((1+\varepsilon)(1 + \ln(\Delta+1))\) approximation algorithms for any \(\varepsilon > 1/\mathrm{polylog}\Delta\) in the \(\mathsf{CONGEST}\) model with \(2^{O(\sqrt{\log n \log\log n})}\) and \(O((\Delta + \log^* n) \cdot \mathrm{polylog}\Delta)\) round complexity respectively. The round complexity \(2^{O(\sqrt{\log n \log\log n})}\) in [5] can be reduced to \(O(\mathrm{poly} \log n)\) by using improved deterministic algorithms such as [6] for computing a network decomposition of \(G^2\).³ Faour, Ghaffari, Grunau, Kuhn, and Rozhoň [7] achieved a deterministic \(O(\log \Delta)\) approximation in \(\tilde{O}(\log^3 \Delta + \log^* n)\) rounds.⁴ If we allow exponential-time local computation, Ghaffari, Kuhn, and Maus [8] showed that it is possible to achieve \((1+o(1))\) approximation in poly-logarithmic rounds in the \(\mathsf{LOCAL}\) model, which can be derandomized with the network decomposition of [6]. On the lower bound side, Kuhn, Moscibroda, and Wattenhofer [9] showed that achieving a poly-logarithmic approximation in the \(\mathsf{LOCAL}\) model requires \[\min \{\Omega( \log \Delta/ \log\log \Delta ), \Omega( \sqrt{\log n/ \log \log n})\}\] rounds.

1.0.0.3 Distributed MDS on Special Graph Families.

The MDS problem has been under significant attention on a variety of special graph families, such as planar graphs, bounded genus graphs, bounded expansion graphs, bounded arboricity graphs (which is the focus of our paper), and more (see, e.g. [10]–[25]).

1.0.0.4 Graphs of Bounded Arboricity.

The arboricity of a graph is the smallest number of forests into which the edges of the graph can be partitioned. It is believed that some natural real world graphs, such as the world wide web graph, social networks, and transaction networks have bounded arboricity. This led to extensive research on this family of graphs not only in the distributed setting but also in other settings such as streaming, dynamic, and sublinear (see e.g. [4], [14], [24], [26]–[55]).

1.0.0.5 Distributed MDS on Graphs of Bounded Arboricity.

The first algorithm for MDS on bounded arboricity graphs was introduced by Lenzen and Wattenhofer [14], who gave two algorithms, a randomized \(O(\alpha^2)\) approximation and a deterministic \(O(\alpha \log \Delta)\) approximation in \(O(\log n)\) and \(O(\log \Delta)\) round complexity respectively. Later, Amiri [21] provided a deterministic \(O(\alpha^2)\) approximation in \(O(\log n)\) rounds. None of these algorithms require prior knowledge of the value of \(\alpha\). Bansal and Umboh [32] showed that it is NP-Hard to achieve \(\alpha-1-\varepsilon\) approximation and provided a centralized \(3\alpha\) approximation LP based algorithm that can be improved to \((2\alpha+1)\) approximation by optimizing the parameters [56]. Together with the \((1+\varepsilon)\) approximation of Kuhn, Moscibroda, and Wattenhofer [4] for solving the LP, it is possible to implement the centralized algorithm of [32] in the \(\mathsf{CONGEST}\) model to achieve \((2\alpha+1)(1+\varepsilon)\) approximation in \(O(\varepsilon^{-4}\log^2\Delta)\) rounds. This algorithm needs prior knowledge of the value of \(\alpha\). Morgan, Solomon, and Wein [44] provided an \(O(\alpha)\) approximation in \(O(\alpha \log \Delta)\) rounds that needs prior knowledge of \(\alpha\). Dory, Ghaffari, and Ilchi [24] provided a deterministic \((2\alpha+1)(1+\varepsilon)\) approximation and a randomized \(\alpha(1+o(1))\) approximation in \(O(\varepsilon^{-1}\log\Delta)\) and \(O(\alpha \log \Delta/\log \alpha)\) rounds respectively. These algorithms need prior knowledge of \(\alpha\). [24] also described a deterministic \((4\alpha+2)(1+\varepsilon)\) approximation in \(O(\varepsilon^{-1}\log n)\) rounds without prior knowledge of \(\alpha\). All of the aforementioned results work in the \(\mathsf{CONGEST}\) model.

On the lower bound side, [24] showed that one needs at least \(\Omega(\log\Delta/\log\log\Delta)\) rounds to obtain any constant or poly-logarithmic approximation, even in the \(\mathsf{LOCAL}\) model and even in the case where \(\alpha=2\). Although many of the previous results have a near-optimal round complexity of \(O(\log\Delta)\), one can ask the following natural question.

The same question has been studied for related classic problems, such as minimum vertex-cover (more generally, minimum set-cover), and maximum matching (See [57]–[59]).

1.1 Technical Overview↩︎

Our main result is as follows.

Our algorithm runs in the optimal number of rounds among all algorithms that achieve a poly-logarithmic approximation factor due to the lower bound of [24]. The message size of our algorithm is optimal as well. Moreover, our algorithm has the best approximation ratio among all previous results in the optimal round complexity of \(O(\log\Delta/\log\log\Delta)\), when the value of \(\alpha\) is unknown, but the value of \(\Delta\) is known to the algorithm. We achieve our result by providing a deterministic algorithm for the distributed minimum dominating set problem on graphs of bounded arboricity that has a trade-off between the approximation ratio and the round complexity in 2.

By plugging \(\beta = \Theta \left( \frac{\log\Delta}{\log\log\Delta} \right)\) in the above theorem, we get \(O\!\left(\alpha \cdot \frac{\log \Delta}{\log\log\Delta}\right)\)-approximation in \(O\!\left(\frac{\log \Delta}{\log\log\Delta}\right)\) rounds, which concludes 1. Our algorithm for 2 works as follows. It runs in \(\log_\beta(\Delta+1)\) iterations from \(i = 1\) up to \(\log_\beta(\Delta+1)\), and builds a dominating set \(S\). At iteration \(i\), every undominated (by \(S\)) node \(u \in V\) votes for one of its neighbors that dominates at least \((\Delta+1)/\beta^i\) undominated nodes (if any). Then, every node that has been voted at least once, becomes part of the solution \(S\).

Comparison to [14]. One of the algorithms by Lenzen and Wattenhofer [14] achieves a trade-off between the approximation ratio and the round complexity as follows. For any \(\beta \geq 2\), it is possible to get \(O(\alpha\beta\log_\beta \Delta)\) approximation in \(O(\log_\beta \Delta)\) rounds with message size bounded by \(O(\log\log_\beta\Delta)\).⁵ Hence, by letting \(\beta = \log^\epsilon \Delta\), one achieves a \(O(\alpha \varepsilon^{-1} \log^{1+\varepsilon}\Delta/\log\log\Delta)\) approximation in \(O(\varepsilon^{-1}\log\Delta/\log\log\Delta)\) rounds with \(O(\log(\varepsilon^{-1}\log\Delta))\) message size.

The algorithm works as follows. Every undominated node \(u\in V\) considers its residual degree (defined as the number of undominated nodes that can be dominated by \(u\) at this point in time), and if its residual degree is within a factor \(2\) of the maximum residual degree of all nodes in its 2-hop neighborhood (nodes of distance at most \(2\) of \(u\)), then \(u\) becomes one of the candidates to be part of the solution. Then, each undominated node votes for one of the candidates in its neighborhood (if any) arbitrarily, and the voted node becomes part of the solution.

Our algorithm is a simplification of this result. Instead of considering the 2-hop neighborhood of a node \(u\) to determine if \(u\) is a candidate, we simply consider each \(u\) as a candidate if it dominates \(\tau\) many undominated nodes at this point in time, where \(\tau\) is a threshold that decreases geometrically over time. We provide the approximation ratio analysis of this simplified algorithm, which is also stronger than the approximation ratio of the specified algorithm of [14]. More precisely, the approximation ratio is reduced from \(O(\alpha\beta\log\Delta)\) to \(O(\alpha(\beta+\log\Delta))\).

The only downside of our algorithm compared to [14] is the assumption of prior knowledge of \(\Delta\). Let us also mention that, in Theorem 2 of [14], it is stated that the approximation ratio of their algorithm is tight. As a result, some modifications to [14] is necessary to hope for a better approximation ratio.

Comparison to [21] and [24]. In the case of unknown \(\alpha\), both of [21] and [24] first apply the algorithm of Barenboim and Elkin [13] to compute a so called forest decomposition, i.e. an orientation of the edges of the graph is computed in \(O(\varepsilon^{-1}\log n)\) rounds such that the out-degree of each node is at most \((2+\varepsilon)\alpha\). It is not obvious at all how we can get around this step since both of the algorithms in [21] and [24] heavily depend on this step. In [21], the algorithm needs this decomposition to construct a set-cover instance whose solution translates to a minimum dominating set in the original graph. In [24], every node computes a local approximation of the arboricity according to the decomposition and uses this approximate value for its own decisions (See Remark 4.5 in the arXiv version of [24] for more details). On the other hand, our algorithm does not need the decomposition or any information about \(\alpha\). We should mention that the algorithm of [24] is simple and elegant, and if we assume prior knowledge of \(\alpha\), one can get a \(O(\alpha\log^{\varepsilon}\Delta)\) approximation in \(O(\varepsilon^{-1}\log \Delta / \log\log \Delta)\) rounds. In [24] the result is stated as \((2\alpha+1)(1+\varepsilon)\) approximation in \(O(\varepsilon^{-1}\log \Delta)\) rounds, but the actual round complexity is \(\log_{1+\varepsilon} \Delta\) and the parameter \(\varepsilon\) here does not need to be close to zero. It remains to replace \(1 + \varepsilon \gets \log^\varepsilon \Delta\) to get the mentioned result.

1.1.0.1 Summary of Known Results.

1 summarizes the results for MDS on graphs of arboricity \(\alpha\) in the case where the value of \(\alpha\) is unknown to the algorithm. A more comprehensive table is provided in 3.

1.2 Preliminaries↩︎

Let \(G = (V, E)\) be a simple undirected graph. For every node \(v \in V\), we denote by \(N(v)\) the set of neighbors of \(v\), and define \(N^+(v) := N(v) \cup \{v\}\). For each subset of nodes \(U \subseteq V\), we define \(N^+(U) = \cup_{u \in U} N^+(u)\). For each two subsets of nodes \(U,C \subseteq V\), we define \(N^+(U,C) := N^+(U) \cap C\). For every \(U \subseteq V\), let \(E[U]\) be the set of edges whose both endpoints belong to \(U\), i.e. \(E[U] := \{uv \in E \mid u,v \in U\}\). We denote the arboricity of \(G\) by \(\alpha(G)\), which is defined as the minimum number of forests into which \(E\) can be partitioned. According to the well-known Nash-Williams’ theorem [60], we have \[\label{eq:arboricity-formula} \alpha(G) = \max_{U \subseteq V, \;|U|\geq 2} \left\lceil \frac{|E[U]|}{|U|-1} \right\rceil.\tag{1}\]

2 Achieving \(O\!\left(\alpha (\beta + \log_\beta \Delta)\right)\)-Approximation in \(O\!\left( \log_\beta \Delta\right)\) Rounds↩︎

In this section, we provide the algorithm for 2 together with its analysis.

2.1 Description of the Algorithm↩︎

Initially, we let \(S = \emptyset\) and all nodes are undominated. Throughout the algorithm, \(S\) represents the set of selected nodes so far to be part of the output dominating set, and a node \(u\) is dominated if and only if \(u \in N^+(S)\). Fix any arbitrary parameter \(\beta > 1\). The algorithm runs in \(\ell := \lceil \log_\beta (\Delta+1) \rceil\) iterations. In the \(i^\mathrm{th}\) iteration, every undominated node \(u \notin N^+(S)\) votes for one node \(p_u\) in its neighborhood \(p_u \in N^+(u)\) that covers at least \((\Delta+1) / \beta^i\) undominated nodes (if any). Then \(p_u\) will be added to the solution \(S\).

More precisely, at the beginning of iteration \(i\), every node \(u\) knows which of its neighbors are dominated. Then, we have the following procedure during iteration \(i\).

1. Every node \(u\) computes \(\deg^{(i)}(u) := |N^+(u) \setminus N^+(S)|\), i.e. the number of undominated nodes in \(N^+(u)\). Then, \(u\) informs its neighbors, whether or not this value is greater than or equal to \((\Delta+1)/\beta^i\).

2. Every undominated node \(u\) considers all elements in \(N^+(u)\) and votes for a node \(p_u \in N^+(u)\) that has \(\deg^{(i)}\) value greater than or equal to \((\Delta+1)/\beta^i\), breaking the ties arbitrarily. Note that \(p_u\) might be equal to \(u\) itself. If no such element exists (which means for all \(v \in N^+(u)\) we have \(\deg^{(i)}(v) < (\Delta+1)/\beta^i\)), we let \(p_u = \bot\). Now, if \(p_u \neq \bot\), then \(u\) informs \(p_u\) that it is voted to be part of the solution.

3. Each voted node \(v\) (i.e., there exists an undominated \(u\) such that \(v=p_u\)) informs all of its neighbors that \(v\) is voted and is now part of the solution \(S\). Hence, \(S \gets S + v\), and the neighbors of \(v\) mark themselves as dominated. Note that this step happens simultaneously, and many nodes might be added to \(S\).

4. Every node \(u\) informs its neighbors whether \(u\) is dominated or undominated at this point.

2.2 Analysis↩︎

2.2.0.1 Correctness.

According to Step 4 of the iteration, it is obvious that at the beginning of each iteration, every node \(u\) correctly knows which of its neighbors are dominated. It is easy to see that, conditioned on the previous knowledge, the values of \(\deg^{(i)}\) are computed correctly, every node correctly knows whether or not it is a candidate, every node correctly knows whether it has been voted, and every node knows whether it is dominated correctly at the end of the iteration.

The algorithm runs while \(i \leq \ell = \lceil \log_\beta(\Delta+1) \rceil\). Note that we have \((\Delta+1)/ \beta^{\ell} \leq 1\). This concludes that in the last iteration of the algorithm, for every undominated node \(u\), we have \(p_u \neq \bot\) (since at least \(u\) itself satisfies \(\deg^{(i)}(u) \geq 1 \geq (\Delta+1)/ \beta^{\ell}\)), and \(u\) will be dominated at the end of this iteration. This concludes that the final solution \(S\) of the algorithm is indeed a dominating set.

2.2.0.2 Round Complexity.

Clearly, each of the Steps in every iteration can be done in only one round simultaneously for all nodes. This concludes that the algorithm runs in \(4 \cdot \left\lceil \log_\beta (\Delta+1) \right\rceil\) rounds.

2.2.0.3 Message Sizes.

The size of the messages between each pair of neighbors in each round is only one bit, since in each step of each iteration, every node \(u\) only needs to notify its neighbors about the correctness of a condition. In the first step, every node \(u\) only needs to notify its neighbors whether or not the condition \(\deg^{(i)}(u) \geq (\Delta+1)/\beta^i\) holds. In the second step, every node \(u\) only needs to notify \(p_u\) that it has been voted for by \(u\) (and notify other neighbors that they have not been voted for by \(u\)). In the third step, each node \(u\) notifies its neighbors whether or not \(u \in S\). In the fourth step, each node \(u\) notifies its neighbors whether or not \(u\) is dominated. Hence, every round of the algorithm only needs one bit of communication for each pair of neighbors.

2.3 Approximation Ratio Analysis↩︎

Let \(D^\star\) be an optimum dominating set. We consider a partition on the solution \(S = S_1 \cup \cdots \cup S_\ell\) (recall that \(\ell = \lceil \log_\beta(\Delta+1) \rceil\)), where \(S_i\) consists of the nodes that became part of the solution during iteration \(i\) of the algorithm. For simplicity, define \(S_0 := \emptyset\). For each \(1 \leq i \leq \ell\), let \(C_i\) be the set of nodes that became dominated at the end of iteration \(i\) of the algorithm, i.e., \(C_i := N^+(S_i) \setminus N^+(S_0 \cup \cdots \cup S_{i-1})\). Hence, \(C_1, \ldots, C_\ell\) form a partition of \(V\). For simplicity, define \(C_0 := \emptyset\).

The analysis consists of two parts. In the first part, we show that at the end of each iteration, the number of newly dominated nodes is proportional to the number of nodes that become part of the solution, i.e. \(|S_i|\) is proportional to \(|C_i|\). This shows that the choices of the algorithm were good during iteration \(i\). In the second part, we analyze the contribution of the optimum solution while dominating each \(C_i\). We start with the following claim.

For each \(1 \leq i \leq \ell\), assume that \(D_i\) is the set of nodes in the optimum solution \(D^\star\) that dominate at least one node in \(C_i\), but do not dominate any node in \(C_0 \cup \cdots \cup C_{i-1}\), i.e., \(D_i := D^\star \cap \left( N^+(C_i) \setminus N^+(C_0 \cup \cdots \cup C_{i-1}) \right)\). It is easy to see that \(D_1, \ldots, D_\ell\) is a partition of \(D^\star\). For each \(1 \leq i \leq \ell\), we split \(D_i\) into two subsets \(D_i'\) and \(D_i'':= D_i - D_i'\) as follows. \(D_i'\) is the set of nodes in \(D_i\) that does not dominate any node outside \(C_{i}\), i.e., \(D_i' := D_i \cap \left( N^+(C_i) \setminus N^+(C_{i+1} \cup \cdots \cup C_{\ell}) \right)\). Intuitively, \(D_i'\) does not contribute to dominating any node outside \(C_i\). But, \(D_i''\) has the potential to contribute to dominating nodes in \(C_j\) for \(j > i\). 1 illustrates the connection between these objects. Note that for the last index \(i = \ell\), we always have \(D_\ell'' = \emptyset\) since \(D^\star\) is a dominating set.

Finally, we get an upper bound on the approximation ratio of our algorithm as follows. Combining 2 and 2, we have \[\begin{align} |S| &\leq 5\alpha \beta \cdot |D'| + \frac{5\alpha}{\Delta+1}\cdot \sum_{j=1}^\ell \sum_{i=1}^j \beta^j \cdot |N^+(D_i'', C_j)| \\ &= 5\alpha \beta \cdot |D'| + \frac{5\alpha}{\Delta+1}\cdot \sum_{i=1}^\ell \sum_{j=i}^\ell \beta^j \cdot |N^+(D_i'', C_j)| \\ &\leq 5\alpha\beta \cdot |D'| + \frac{5\alpha}{\Delta+1}\cdot \left( \log_\beta(\Delta+1) + \beta \right) \cdot (\Delta+1) \cdot |D''| \\ &\leq 10\alpha \cdot (\beta + \log_\beta (\Delta+1)) \cdot |D^\star|. \end{align}\] This completes the approximation ratio analysis.

3 State-of-the-Art for Distributed Dominating Set on Graphs With Arboricity at Most \(\alpha\)↩︎

References↩︎