# Near-Optimal Distributed Dominating Set
in Bounded Arboricity Graphs

Michal Dory
<EMAIL_ADDRESS>
ETH Zurich  Mohsen Ghaffari
<EMAIL_ADDRESS>
ETH Zurich  Saeed Ilchi
<EMAIL_ADDRESS>
ETH Zurich

###### Abstract

We describe a simple deterministic $O(\varepsilon^{-1}\log\Delta)$ round
distributed algorithm for $(2\alpha+1)(1+\varepsilon)$ approximation of
minimum weighted dominating set on graphs with arboricity at most $\alpha$.
Here $\Delta$ denotes the maximum degree. We also show a lower bound proving
that this round complexity is nearly optimal even for the unweighted case, via
a reduction from the celebrated KMW lower bound on distributed vertex cover
approximation [Kuhn, Moscibroda, and Wattenhofer JACM’16].

Our algorithm improves on all the previous results (that work only for
unweighted graphs) including a randomized $O(\alpha^{2})$ approximation in
$O(\log n)$ rounds [Lenzen and Wattenhofer DISC’10], a deterministic
$O(\alpha\log\Delta)$ approximation in $O(\log\Delta)$ rounds [Lenzen and
Wattenhofer DISC’10], a deterministic $O(\alpha)$ approximation in
$O(\log^{2}\Delta)$ rounds [implicit in Bansal and Umboh IPL’17 and Kuhn,
Moscibroda, and Wattenhofer SODA’06], and a randomized $O(\alpha)$
approximation in $O(\alpha\log n)$ rounds [Morgan, Solomon and Wein DISC’21].

We also provide a randomized $O(\alpha\log\Delta)$ round distributed algorithm
that sharpens the approximation factor to $\alpha(1+o(1))$. If each node is
restricted to do polynomial-time computations, our approximation factor is
tight in the first order as it is NP-hard to achieve $\alpha-1-\varepsilon$
approximation [Bansal and Umboh IPL’17].

##  1 Introduction

The minimum dominating set (MDS) problem is a classic and central problem in
graph algorithms. In this problem, the goal is to construct a minimum weight
set of nodes $S$ such that each node is either in $S$ or has a neighbor in
$S$. The MDS problem has been widely studied both in the classic centralized
setting and in the distributed setting, and it has various applications, for
example, clustering and routing in ad-hoc networks. It is well-known that a
simple greedy algorithm gives $\ln{(\Delta+1)}$ approximation for the problem
for graphs with maximum degree $\Delta$ [Joh74], and that it is NP-hard to
obtain a $c\ln{\Delta}$-approximation for a suitable constant $c$ [DS14]. A
similar approximation can be also obtained by efficient distributed algorithms
[JRS02, KW05, KMW06, DKM19]. In particular, Kuhn, Moscibroda, and Wattenhofer
showed a randomized $O(\log{\Delta})$-approximation algorithm that takes
$O(\log^{2}{\Delta})$ rounds in the $\mathsf{CONGEST}$ model, where messages
are restricted to $O(\log{n})$ bits, or $O(\log{n})$ rounds in the
$\mathsf{LOCAL}$ model, where the message size is unbounded [KMW06]. There is
also a deterministic poly-logarithmic $O(\log{\Delta})$-approximation
algorithm for the problem in $\mathsf{CONGEST}$ that is obtained by combining
the algorithm of Deurer, Kuhn, and Maus [DKM19] with the recent deterministic
network decomposition of Rozhoň and Ghaffari [RG20]. If one allows unbounded
messages and exponential local computation, one can obtain even
$(1+\varepsilon)$-approximation for the problem in poly-logarithmic time in
the $\mathsf{LOCAL}$ model using the algorithm of Ghaffari, Kuhn, and Maus
[GKM17]. On the lower bound side, Kuhn, Moscibroda, and Wattenhofer showed
that one needs $\Omega(\log{\Delta}/\log{\log{\Delta}})$ rounds or
$\Omega(\sqrt{\log{n}/\log{\log{n}}})$ rounds (the minimum of these two lower
bounds applies) to get a logarithmic approximation [KMW16].

Since it is NP-hard to obtain better than logarithmic approximation in general
graphs, a large body of research focused on finding algorithms with a better
approximation in special graph families, such as planar graphs, graphs of
bounded expansion, and more (see, e.g., [LPW13, AAOdMRS18, ASS19, BCGW21,
CHW08, LOW08, Waw14]). One prominent example is the class of _bounded
arboricity_ graphs, which informally speaking are graphs that are sparse
everywhere. The arboricity $\alpha$ of a graph is the minimum number of
forests into which its edges can be partitioned. The class of bounded
arboricity graphs includes many important graph classes such as planar graphs,
graphs of bounded treewidth or genus, and graphs excluding a fixed minor. Many
real-world graphs are sparse and believed to have low arboricity, for example,
the World Wide Web graph and graphs representing social networks. This led to
extensive study of graph problems in low-arboricity graphs (see, e.g., [GG06,
LW10, BU17, MSW21, ELR20, GBSH21, CCMU21]).

###  1.1 MDS in Bounded Arboricity Graphs

Lenzen and Wattenhofer showed the first algorithms for MDS in bounded
arboricity graphs [LW10]. In particular, they showed a randomized
$O(\alpha^{2})$-approximation algorithm that takes $O(\log{n})$ time, and a
deterministic $O(\alpha\log{\Delta})$-approximation algorithm that takes
$O(\log{\Delta})$ time. An $O(\alpha^{2})$-approximation can be also obtained
deterministically in $O(\log{n})$ time as was shown recently by Amiri [Ami21].
All these algorithms work in the $\mathsf{CONGEST}$ model. A recent line of
work shows $O(\alpha)$-approximation algorithms for the problem. First, a
centralized algorithm of Bansal and Umboh gives $(2\alpha+1)$-approximation
for the problem [BU17].111The paper claimed a $3\alpha$-approximation, but
optimizing the parameters of the algorithm gives a
$(2\alpha+1)$-approximation, as was observed by Dvořák [Dvo19]. They also show
that it is NP-hard to obtain an $(\alpha-1-\epsilon)$-approximation for the
problem. The algorithm of Bansal and Umboh is based on LP-rounding, and can be
implemented efficiently in the $\mathsf{CONGEST}$ model using an algorithm for
approximating the LP. This leads to a deterministic
$O(\log^{2}{\Delta}/\varepsilon^{4})$-round
$(2\alpha+1)(1+\epsilon)$-approximation algorithm using the
$(1+\epsilon)$-approximation algorithm of Kuhn, Moscibroda, and Wattenhofer
for approximating the LP [KMW06]. A recent combinatorial algorithm for MDS in
bounded arboricity graphs was shown by Morgan, Solomon and Wein [MSW21]; they
obtain a randomized $O(\alpha\log{n})$-round $O(\alpha)$-approximation
algorithm for the problem in $\mathsf{CONGEST}$. All the above algorithms
solve the unweighted version of the problem. Lastly, a very recent centralized
algorithm of Sun [Sun21] gives an $(\alpha+1)$-approximation for the weighted
version of the problem. This algorithm however seems inherently sequential and
does not seem to translate to an efficient distributed algorithm (see Section
1.3 for a more detailed discussion).

###  1.2 Our Contribution

Our first contribution is showing that $O(\alpha)$-approximation for weighted
MDS can be obtained in just $O(\log{\Delta})$ rounds in the $\mathsf{CONGEST}$
model. In particular, we show a simple deterministic algorithm that gives the
following. For this and all the other algorithms in this paper, we assume that
both $\Delta$ and $\alpha$ are known to all nodes. Please see Remark 4.4 and
Remark 4.5 for a discussion on the setting where $\Delta$ and $\alpha$ are
unknown.

######  Theorem 1.1.

For any $0<\varepsilon<1$, there is a deterministic
$(2\alpha+1)(1+\varepsilon)$-approximation algorithm for the minimum weighted
dominating set problem in graphs with arboricity at most $\alpha$. The
algorithm runs in $O\left(\frac{\log(\Delta/\alpha)}{\varepsilon}\right)$
rounds in the $\mathsf{CONGEST}$ model.

Our algorithm is faster compared to the two previous $O(\alpha)$-approximation
algorithms that take $O(\log^{2}{\Delta}/\varepsilon^{4})$ rounds [BU17,
KMW06] and $O(\alpha\log{n})$ rounds [MSW21], and its $O(\log\Delta)$
complexity is nearly optimal, as we will discuss later when describing lower
bounds. Its approximation ratio of $(2\alpha+1)(1+\varepsilon)$ matches the
best approximation that was previously obtained by a distributed algorithm. It
is a deterministic algorithm, where the previous $O(\alpha\log{n})$ round
algorithm was randomized. Moreover, to the best of our knowledge, our
algorithm is the first distributed algorithm that solves the _weighted_
version of the problem.

#### Improved Approximation

We also show a randomized algorithm with an improved approximation of
$\alpha(1+o(1))$, giving the following.

######  Theorem 1.2.

For any $1\leq t\leq\frac{\alpha}{\log\alpha}$, there is a randomized
algorithm with expected $(\alpha+O(\frac{\alpha}{t}))$-approximation factor
for the minimum weighted dominating set problem in graphs with arboricity at
most $\alpha$. The algorithm runs in $O(t\log\Delta)$ rounds in the
$\mathsf{CONGEST}$ model.

In particular, by setting $t=\frac{\alpha}{\log\alpha}$, we can get
$(\alpha+O(\log{\alpha}))$-approximation in $O(\alpha\log{\Delta})$ time. For
algorithms that are only using polynomial time computations, this
approximation factor is tight in the first order as it is NP-hard to achieve
$\alpha-1-\varepsilon$ approximation [BU17].

As a byproduct of our randomized algorithm, we improve on the approximation
factor for the minimum dominating set problem on general graphs with maximum
degree $\Delta$. Previously, the best approximation factor for the problem in
$O(k^{2})$ (for a parameter $k$) rounds was due to the work of Kuhn,
Moscribroda, and Wattenhofer [KMW06] where they provided a randomized
algorithm with expected approximation factor
$O(k\Delta^{\frac{2}{k}}\log\Delta)$. We drop the $O(\log\Delta)$ term in
their result.

######  Theorem 1.3.

For any $k$, there is randomized algorithm that computes a weighted dominating
set with expected approximation factor at most
$\Delta^{\frac{1}{k}}(\Delta^{\frac{1}{k}}+1)(k+1)\cdot=O(k\Delta^{\frac{2}{k}})$
in $O(k^{2})$ rounds in the $\mathsf{CONGEST}$ model.

#### Lower Bound

Our algorithms provide $O(\alpha)$-approximation in $O(\log{\Delta})$ rounds.
A natural question is whether a logarithmic dependence on $\Delta$ is needed
in the time complexity. While in general graphs it is known that
$\Omega(\log{\Delta}/\log{\log{\Delta}})$ rounds are required for obtaining a
constant or logarithmic approximation [KMW16], in special graph families
faster algorithms are known. For example, in planar graphs one can obtain
$O(1)$-approximation in $O(1)$ rounds in the $\mathsf{LOCAL}$ model [LOW08,
Waw14]. Also, in the special case of trees that have arboricity 1, a trivial
algorithm that takes all non-leaf nodes gives a 3-approximation for unweighted
MDS (see Appendix A for the proof). Interestingly, we show that as soon as the
arboricity is increased from $1$ to $2$, the locality of the minimum
dominating set approximation problem changes radically, and any constant or
poly-logarithmic approximation needs
$\Omega\left(\frac{\log\Delta}{\log\log\Delta}\right)$ time, even in the
$\mathsf{LOCAL}$ model where the size of messages is unbounded.

######  Theorem 1.4.

Any distributed algorithm that computes any constant or poly-logarithmic
approximation of the minimum dominating set on graphs of arboricity 2 requires
$\Omega\left(\frac{\log\Delta}{\log\log\Delta}\right)$ rounds in the
$\mathsf{LOCAL}$ model.

Hence, the $O(\log\Delta)$ round complexity of our algorithms is nearly
optimal.

###  1.3 Our Techniques

At a high-level, our algorithms construct a dominating set in two steps. In
the first step, we construct a partial dominating set $S$ that has the
following nice properties. First, the weight of the set $S$ is a good
approximation for the optimal dominating set. Second, the nodes $T$ that are
undominated by $S$ have a nice structure that allows us to find efficiently a
dominating set for $T$ with a good approximation guarantee. In the second
step, we construct a dominating set for $T$. In fact, in our first algorithm,
we show that if for each node in $T$ we add one node to the dominating set, we
already obtain a $(2\alpha+1)(1+\varepsilon)$-approximation. In our second
algorithm, we show how to exploit the structure of $T$ to obtain a better
approximation. Our algorithm for constructing the partial dominating set is
inspired by the primal-dual method. To explain the idea, we first describe in
Section 3 a simpler variant of our algorithm that works for unweighted graphs.
Next, in Section 4, we generalize the algorithm for weighted graphs, and also
show our randomized algorithm with improved approximation. Our lower bound
appears in Section 5.

#### Comparison to [Sun21]

We remark that in a very recent independent work [Sun21], the author uses the
primal-dual method to obtain approximation algorithm for MDS in bounded
arboricity graphs in the centralized setting. This algorithm however does not
seem to translate to an efficient distributed algorithm, as it has a reverse-
delete step that makes it inherently sequential. In this step, the algorithm
goes over all the nodes that were added to the dominating set $S$ in reverse
order and removes them from $S$ if it is still a valid dominating set. This
part is crucial for obtaining a good approximation ratio, and the analysis
crucially relies on this part. While in our algorithm we also use the primal-
dual method, we use it in a different way, and only to construct a partial
solution for the problem.

##  2 Preliminaries

The input graph is $G=(V,E)$ with $n$ nodes, $m$ edges, maximum degree
$\Delta$, and arboricity $\alpha$. For each node $v\in V$, let $N_{v}$ be the
set of neighbors of $v$ and $N^{+}_{v}=\\{v\\}\cup N_{v}$. For a set of nodes
$S\subseteq V$, let $N^{+}_{S}=\bigcup_{v\in S}N^{+}_{v}$ be set of nodes that
are dominated by $S$. Let $w_{v}$ be the weight of $v$ and for set $S\subseteq
V$, let $w_{S}=\sum_{v\in S}w_{v}$ be the total weight of the set $S$. We
assume all the weights are positive integers and are bounded by $n^{c}$ for
some constant $c$.

Our algorithms are inspired by the primal-dual method. We associate a packing
value $0\leq x_{v}$ to each node such that for any node $u$, the value
$X_{u}=\sum_{v\in N^{+}_{u}}x_{v}\leq w_{u}$. From weak duality, we have the
following.

######  Lemma 2.1.

For any feasible packing, $\sum_{v\in V}x_{v}\leq\mathrm{OPT}$ where
$\mathrm{OPT}$ is the weight of the minimum dominating set of $G$.

###### Proof.

Let $S^{*}$ be a dominating set of $G$ with weight $\mathrm{OPT}$. We have:

$\mathrm{OPT}=\sum_{v\in S^{*}}w_{v}\geq\sum_{v\in S^{*}}X_{v}\geq\sum_{u\in
V}x_{u}$

The last inequality comes from the fact that $S^{*}$ is a dominating set.
Hence, each node $u$ contributes to at least one of $X_{v}$ for $v\in S^{*}$.
∎

#### Model

Our algorithms work in the standard $\mathsf{CONGEST}$ model. We have a
communication network with $n$ nodes that is identical to the input graph.
Nodes communicate with each other by sending $O(\log{n})$ bit messages in
synchronous rounds. In the beginning, each node only knows its own weight and
set of neighbors. At the end of the algorithm, each node should know if it is
part of the constructed dominating set. Our lower bound works even for the
more powerful $\mathsf{LOCAL}$ model where the size of messages is unbounded.

##  3 Algorithm for Unweighted MDS

As a warm-up, we start by describing a simpler variant of our algorithm that
works for unweighted graphs, showing the following.

######  Theorem 3.1.

For any $0<\varepsilon<1$, there is a deterministic
$(2\alpha+1)(1+\varepsilon)$-approximation algorithm for the minimum
dominating set problem in unweighted graphs with arboricity at most $\alpha$
that runs in $O\left(\frac{\log(\Delta/\alpha)}{\varepsilon}\right)$ rounds in
the $\mathsf{CONGEST}$ model.

Our approach is inspired by the primal-dual method. Each node $v$ has a
packing value $x_{v}$, such that during the algorithm for each node, the value
$X_{v}=\sum_{u\in N^{+}_{v}}x_{u}\leq 1$. From Lemma 2.1 we have that
$\sum_{v\in V}x_{v}\leq\mathrm{OPT}$, where $\mathrm{OPT}$ is an optimal
solution. Our algorithm first builds a partial dominating set $S$ with the
following properties.

######  Lemma 3.2.

For any $0<\varepsilon<1$, there is a deterministic algorithm that takes
$O\left(\frac{\log(\Delta/\alpha)}{\varepsilon}\right)$ rounds and outputs a
partial dominating set $S\subseteq V$ along with packing values
$\\{x_{v}\\}_{v\in V}$ such that

  1. 1.

$|S|\leq(2\alpha+1)(1+\varepsilon)\sum_{v\in N^{+}_{S}}x_{v}$.

  2. 2.

For each node $v\not\in N^{+}_{S}$, we have
$x_{v}\geq\frac{1}{(2\alpha+1)(1+\varepsilon)}$.

Let $T=V\setminus N^{+}_{S}$ be the set of undominated nodes. We next show
that adding the nodes of $T$ to the dominating set $S$ results in the desired
approximation.

######  Claim 3.3.

The set $S\cup T$ is a dominating set of size at most
$(2\alpha+1)(1+\varepsilon)\mathrm{OPT}$.

###### Proof.

The set $S\cup T$ is clearly a dominating set, as we added to $S$ all the
undominated nodes. From Lemma 3.2, we have that

$|S|\leq(2\alpha+1)(1+\varepsilon)\sum_{v\in N^{+}_{S}}x_{v},$ $|T|=\sum_{v\in
T}1\leq(2\alpha+1)(1+\varepsilon)\sum_{v\in T}x_{v}.$

Hence, we get that $|S\cup T|\leq(2\alpha+1)(1+\varepsilon)\sum_{v\in
V}x_{v}\leq(2\alpha+1)(1+\varepsilon)\mathrm{OPT}$, where the last inequality
follows from Lemma 2.1. ∎

To complete the proof, our goal is to prove Lemma 3.2.

###### Proof of Lemma 3.2.

For all nodes, we initialize $x_{v}=\frac{1}{\Delta+1}$. Let $r$ be the
integer such that

$(1+\varepsilon)^{r}\frac{1}{\Delta+1}\leq\frac{1}{(2\alpha+1)(1+\varepsilon)}<(1+\varepsilon)^{r+1}\frac{1}{\Delta+1}$

#### Algorithm for Partial Dominating Set

At the beginning, all the nodes are unmarked. Then, we run the following
procedure for $r+1$ iterations: Per iteration, we run the following on each
node $v$. All nodes run each line simultaneously.

  1. 1.

Compute $X_{v}=\sum_{u\in N^{+}_{v}}x_{u}$.

  2. 2.

If $X_{v}\geq\frac{1}{1+\varepsilon}$, add $v$ to $S$ and mark all the nodes
in $N^{+}_{v}$.

  3. 3.

If $v$ is not marked, set $x_{v}\leftarrow x_{v}(1+\varepsilon)$.

######  Lemma 3.4.

For all nodes, $X_{v}$ is always at most 1.

###### Proof.

At the start of the first iteration,
$X_{v}\leq\frac{|N^{+}_{v}|}{\Delta+1}\leq 1$. At the beginning of iteration
$i\geq 2$, if $v$ is not in $S$, it means $X_{v}<\frac{1}{1+\varepsilon}$ in
iteration $i-1$ and so $X_{v}<1$ in this iteration. If $v$ is in $S$, then
$X_{v}$ is not changed after that and so $X_{v}\leq 1$. ∎

To bound the size of $S$, we use the following property of bounded arboricity
graphs.

######  Observation 3.5.

Let $G$ be a graph with arboricity at most $\alpha$, then the edges of $G$ can
be oriented such that the out-degree of each node is at most $\alpha$.222All
of our algorithms work as long the input graph is orientable with the maximum
out-degree of at most $\alpha$. Hence, our results can be applied to the
slightly larger class of graphs that are decomposable to at most
$\alpha$-pseudoforests. A psuedoforest is a graph in which every connected
component has at most one cycle.

Observation 3.5 follows from the fact that the edges of the graph can be
partitioned into $\alpha$ forests, and in each one of them we can orient the
edges with out-degree one, by fixing a root in each tree and orienting the
edges towards the root. We fix one of those orientations. We emphasize that
this orientation is used only in the analysis, and we do not construct it in
the algorithm. For each node $v$, let $N^{\mathrm{in}}_{v}$ be the set of
incoming neighbors and $N^{\mathrm{out}}_{v}$ be the set of outgoing neighbors
of $v$ with respect to this fixed orientation. Note that for all nodes in
$N^{+}_{S}$, the packing value is increased at most $r$ times. Hence, from the
choice of $r$, we have that $x_{v}\leq\frac{1}{(2\alpha+1)(1+\varepsilon)}$
for $v\in N^{+}_{S}$. For each $v\in S$, we have (all the values $x_{v}$ are
considered at the end of the algorithm):

$\displaystyle X_{v}=\sum_{u\in
N^{\mathrm{in}}_{v}}x_{u}+x_{v}+\sum_{u^{\prime}\in
N^{\mathrm{out}}_{v}}x_{u^{\prime}}$
$\displaystyle\geq\frac{1}{1+\varepsilon}$ $\displaystyle\Rightarrow\sum_{u\in
N^{\mathrm{in}}_{v}}x_{u}$
$\displaystyle\geq\frac{1}{1+\varepsilon}-\frac{\alpha+1}{(2\alpha+1)(1+\varepsilon)}$
$\displaystyle\geq\frac{\alpha}{(2\alpha+1)(1+\varepsilon)}$

Let $\lambda=\frac{\alpha}{(2\alpha+1)(1+\varepsilon)}$. From the above, we
have that $\frac{1}{\lambda}\sum_{u\in N^{\mathrm{in}}_{v}}x_{u}\geq 1$. We
can bound the size of $S$ as follows:

$\displaystyle|S|=\sum_{v\in S}1\leq\frac{1}{\lambda}\sum_{v\in S}\sum_{u\in
N^{\mathrm{in}}_{v}}x_{u}$ $\displaystyle\leq\frac{1}{\lambda}\sum_{u\in
N^{+}_{S}}x_{u}\sum_{v\in S}\mathbb{I}[u\in N^{\mathrm{in}}_{v}]$
$\displaystyle\leq\frac{\alpha}{\lambda}\sum_{u\in N^{+}_{S}}x_{u}$
$\displaystyle\leq(2\alpha+1)(1+\varepsilon)\mathrm{OPT}$

Note that we bound $\sum_{v\in S}\mathbb{I}[u\in N_{v}^{in}]$ with $\alpha$.
This is because the out-degree of $u$ is at most $\alpha$, so $u$ can be an
incoming neighbor of at most $\alpha$ nodes.

To conclude the proof, we should show that for each node $v\not\in N^{+}_{S}$,
we have $x_{v}\geq\frac{1}{(2\alpha+1)(1+\varepsilon)}$. This follows from the
choice of $r$, as for nodes $v\not\in N^{+}_{S}$ we increase the packing value
$r+1$ times.

Each iteration can be implemented in $O(1)$ rounds in the $\mathsf{CONGEST}$
model. In total, $O(r)=O\left(\frac{\log(\Delta/\alpha)}{\varepsilon}\right)$
rounds. ∎

##  4 Algorithm for Weighted MDS

We next show a generalized version of our algorithm from Section 3. First, the
algorithm works for weighted graphs. Second, we allow for different trade-offs
between the two dominating sets we compute in the algorithm. Recall that in
Section 3 we start by computing a partial dominating set $S$, and then we add
to it additional set $S^{\prime}$ to dominate the rest of the nodes.
Previously we just constructed $S^{\prime}$ as the set of all undominated
nodes, but we will see in Section 4.2 an algorithm that exploits the structure
of undominated nodes to get an improved approximation for this part. To get a
better approximation for the whole algorithm, we can stop the algorithm for
computing a partial dominating set earlier and get an improved approximation
for the first part as well. We start by presenting our general scheme, which
allows us to get a deterministic algorithm for weighted graphs with the same
guarantees obtained in Section 3, and then we show a randomized algorithm that
can obtain an improved approximation.

###  4.1 Deterministic Algorithm

We again follow the primal-dual method. We associate a packing value $0\leq
x_{v}$ to each node such that for any node $u$, the value $X_{u}=\sum_{v\in
N^{+}_{u}}x_{v}\leq w_{u}$. For each node $v\in V$, let $\tau_{v}=\min_{u\in
N^{+}_{v}}w_{u}$ be the minimum weight of a node that can dominate $v$.

######  Lemma 4.1.

For any $0<\varepsilon<1$ and $0<\lambda<\frac{1}{(\alpha+1)(1+\varepsilon)}$,
there is a deterministic algorithm that outputs a partial dominating set
$S\subseteq V$ along with packing values $\\{x_{v}\\}_{v\in V}$ with the
following properties:

  1. (a)

$w_{S}\leq\alpha(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\sum_{v\in
N^{+}_{S}}x_{v}$.

  2. (b)

For each undominated node $v\not\in N^{+}_{S}$, its packing value $x_{v}$ is
at least $\lambda\tau_{v}$.

The algorithm runs in $O\left(\frac{\log(\Delta\lambda)}{\varepsilon}\right)$
rounds in the $\mathsf{CONGEST}$ model.

See 1.1

###### Proof.

We run the algorithm of Lemma 4.1 with the same $\varepsilon$ and with
$\lambda$ equals to $\frac{1}{(2\alpha+1)(1+\varepsilon)}$. We want to find a
set $S^{\prime}$ such that $S\cup S^{\prime}$ is a dominating set. For this,
we go over all the undominated nodes $v\not\in N^{+}_{S}$, and add a node from
$N^{+}_{v}$ with weight $\tau_{v}$ to $S^{\prime}$. Clearly, $S\cup
S^{\prime}$ is a dominating set and its weight can be bounded as follows:

$\displaystyle w_{S\cup S^{\prime}}=w_{S}+\sum_{v\in V\setminus
N^{+}_{S}}\tau_{v}$
$\displaystyle\leq\alpha(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\sum_{v^{\prime}\in
N^{+}_{S}}x_{v^{\prime}}+\sum_{v\in V\setminus
N^{+}_{S}}\frac{x_{v}}{\lambda}$
$\displaystyle\leq(2\alpha+1)(1+\varepsilon)\sum_{v\in V}x_{v}$
$\displaystyle\leq(2\alpha+1)(1+\varepsilon)\cdot\mathrm{OPT}$

In the first inequality, we use property (a) of Lemma 4.1 to bound the first
term, and we invoked property (b) of this lemma, i.e. $\lambda\tau_{v}\leq
x_{v}$, to bound the second term. ∎

###### Proof of Lemma 4.1.

For each node $v$, initialize $x_{v}$ to $\frac{\tau_{v}}{\Delta+1}$. This
gives us a feasible packing since for each node $u$:

$X_{u}=\sum_{v\in N^{+}_{u}}x_{v}=\sum_{v\in
N^{+}_{u}}\frac{\tau_{v}}{\Delta+1}\leq\sum_{v\in
N^{+}_{u}}\frac{w_{u}}{\Delta+1}\leq w_{u}$

If $\lambda<\frac{1}{\Delta+1}$, we can satisfy the two required properties by
setting $S$ to the empty set. Assume $\lambda\geq\frac{1}{\Delta+1}$ and let
$r\geq 1$ be the integer that

$(1+\varepsilon)^{r-1}\frac{1}{\Delta+1}\leq\lambda<(1+\varepsilon)^{r}\frac{1}{\Delta+1}$

We run the following procedure for $r$ iterations.

  1. 1.

For each node $u$, compute $X_{u}=\sum_{v\in N^{+}_{u}}x_{v}$.

  2. 2.

If $X_{u}\geq\frac{w_{u}}{1+\varepsilon}$, add $u$ to $S$.

  3. 3.

For each undominated node $v\not\in N^{+}_{S}$, set $x_{v}\leftarrow
x_{v}(1+\varepsilon)$.

######  Observation 4.2.

Through the algorithm, $\\{x_{v}\\}_{v\in V}$ is always a feasible packing.

######  Observation 4.3.

In the end, the packing value of each undominated node, i.e. nodes in
$V\setminus N^{+}_{S}$, is strictly greater than $\lambda\tau_{v}$ and the
packing value of each dominated node is at most $\lambda\tau_{v}$.

###### Proof.

Let $v\in V\setminus N^{+}_{S}$. Its packing value is multiplied by
$1+\varepsilon$ in all the $r$ iterations. So its final value is
$(1+\varepsilon)^{r}\frac{\tau_{v}}{\Delta+1}>\lambda\tau_{v}$. If $v\in
N^{+}_{S}$, it is multiplied by $1+\varepsilon$ at most $r-1$ times. So its
final value is at most
$(1+\varepsilon)^{r-1}\frac{\tau_{v}}{\Delta+1}\leq\lambda\tau_{v}$. ∎

To bound $w_{S}$, we use Observation 3.5 and orient the edges of $G$ such that
the out-degree of each node is at most $\alpha$. The orientation is used only
for the analysis. For each node $v$, let $N^{\mathrm{in}}_{v}$ be the set of
incoming neighbors and $N^{\mathrm{out}}_{v}$ be the set of outgoing neighbors
of $v$ in this fixed orientation.

Consider the packing values at the end of the algorithm. Note that through the
algorithm, we freeze the packing value of a node as soon as it gets dominated.
With this, we can write the following for each node $u\in S$:

$\displaystyle X_{u}=\sum_{v\in
N^{\mathrm{in}}_{u}}x_{v}+x_{u}+\sum_{v^{\prime}\in
N^{\mathrm{out}}_{u}}x_{v^{\prime}}\geq\frac{w_{u}}{1+\varepsilon}$
$\displaystyle\Rightarrow\sum_{v\in
N^{\mathrm{in}}_{u}}x_{v}\geq\frac{w_{u}}{1+\varepsilon}-\lambda\tau_{u}-\sum_{v^{\prime}\in
N^{\mathrm{out}}_{u}}\lambda\tau_{v^{\prime}}\geq
w_{u}(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))$

This implies:

$\displaystyle\begin{split}w_{S}=\sum_{u\in S}w_{u}&\leq\sum_{u\in
S}(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\sum_{v\in
N^{\mathrm{in}}_{u}}x_{v}\\\
&\leq(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\sum_{v\in
N^{+}_{S}}x_{v}\sum_{u\in S}\mathbb{I}[v\in N^{\mathrm{in}}_{u}]\\\
&\leq\alpha(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\sum_{v\in
N^{+}_{S}}x_{v}\end{split}$ (1)

In the last inequality, we upper bound $\sum_{u\in S}\mathbb{I}[v\in
N_{u}^{in}]$ with $\alpha$. This is because out-degree of $v$ is at most
$\alpha$, so $v$ can be an incoming neighbor of at most $\alpha$ nodes.

The bound of Eq. 1 along with Observation 4.3 guarantee property (a) and
property (b). The only remaining component is the round complexity. Note that
each iteration of the procedure runs in $O(1)$ rounds in the
$\mathsf{CONGEST}$ model. So in total, there are
$O(r)=O(\log_{1+\varepsilon}\Delta\lambda)=O\left(\frac{\log(\Delta\lambda)}{\varepsilon}\right)$
many rounds. ∎

######  Remark 4.4 (Unknown $\Delta$).

We can transform the algorithm of Theorem 1.1 into one that works in the
setting where $\Delta$ is unknown. Recall that the algorithm has two phases.
In the first phase, it computes a partial dominating set $S$ by applying the
algorithm of Lemma 4.1 with $\lambda$ being
$\frac{1}{(2\alpha+1)(1+\varepsilon)}$. Then, in the second phase, for each
node $v$ that is not dominated by $S$, we add a node with weight $\tau_{v}$
from $N^{+}_{v}$ to the final dominating set. To convert our algorithm, first
we initialize the packing value $x_{v}$ of each node $v$ with

$\frac{\tau_{v}}{\max_{u\in N^{+}_{v}}|N^{+}_{u}|}$

rather than with $\frac{\tau_{v}}{\Delta+1}$. Next, we run the iterations of
the algorithm of Lemma 4.1 similarly with one extra step at the beginning of
each iteration. In this extra step, each undominated node $v$ with a packing
value strictly larger than $\lambda\tau_{v}$ adds a node with weight
$\tau_{v}$ in its neighborhood to the final dominating set. Observe that after
$O(\frac{\log\Delta}{\varepsilon})$ rounds, all nodes are dominated and the
approximation analysis goes through similarly. Intuitively, since a node
cannot decide locally when the first phase terminates, we add this extra step
for each iteration to simulate its effect.

######  Remark 4.5 (Unknown $\alpha$).

When $\alpha$ is unknown, we are not aware of a way to keep the algorithm’s
round complexity independent of $n$, while preserving the approximation
factor. However, we can find a dominating set with approximation factor
$(2\alpha+1)(2+\varepsilon)$ in $O(\frac{\log n}{\varepsilon})$ rounds (note
that here we assume that all nodes know $n$). For that, first we apply the
orientation algorithm of Barenboim and Elkin [BE10] to find an orientation of
edges where the out-degree of each node is at most $(2+\varepsilon)\alpha$.
This algorithm runs in $O(\frac{\log n}{\varepsilon})$ rounds. Next, each node
$v$ computes a local approximation of arboricity, denoted by
$\hat{\alpha}_{v}$, for itself which is the maximum out-degree of the nodes in
$N^{+}_{v}$. To find the partial dominating set $S$, each node initializes its
packing value with $\frac{1}{n+1}$. We run the algorithm of Lemma 4.1 where
each node has its own $\lambda$, denoted by $\lambda_{v}$, and which equals
$\lambda_{v}=\frac{1}{(2\hat{\alpha}+1)(1+\varepsilon)}$. Similar to Remark
4.4, we add an extra step in the beginning of each iteration on which any
undominated node $v$ with a packing value more than threshold
$\lambda_{v}\tau_{v}$, adds a node with weight $\tau_{v}$ in $N^{+}_{v}$ to
the final dominating set. After $O(\frac{\log n}{\varepsilon})$ iterations,
all nodes are dominated and the approximation factor is
$(2\alpha+1)(2+O(\varepsilon))$.

###  4.2 Randomized Algorithm

In the previous section, to extend our partial dominating set $S$ to a
dominating set, we simply added one node to $S$ for each undominated node and
this introduced a factor $2$ in the approximation factor. Here, we show how we
can get $\alpha+O(\log\alpha)$ approximation, but we need
$O(\frac{\alpha}{\log\alpha}\log\Delta)$ rounds rather than $O(\log\Delta)$
rounds. The algorithm also becomes randomized.

To reduce the approximation factor, we can leverage property (b) of Lemma 4.1.
To explain the intuition, we focus first on the unweighted case. If the
problem is unweighted (so $\tau_{v}$ is 1 for all the nodes), then property
(b) implies that each node has at most $\lambda^{-1}$ undominated neighbors.
The reason is that $X_{u}=\sum_{v\in N^{+}_{u}}x_{v}\leq 1$ for all $u$. Now
since any node $v\not\in N^{+}_{S}$ has $x_{v}\geq\lambda$, there can only be
at most $\lambda^{-1}$ undominated nodes in $N^{+}_{u}$. So, dominating the
set of nodes that are not in $N^{+}_{S}$ is a set cover problem with maximum
set size $\lambda^{-1}$ which can be approximated with a factor of
$O(\log\lambda^{-1})$ in $O(\log\lambda^{-1}\log\Delta)$ rounds according to
[KMW06] (Note that an undominated node can be a neighbor of many dominated
nodes, so the frequency in the set cover instance can be as large as
$\Delta+1$). Recall that the size of $S$ is bounded by
$\alpha(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\cdot\mathrm{OPT}$. On
the other hand, for extending $S$, we add
$O(\log\lambda^{-1}\cdot\mathrm{OPT})$ many nodes. If we set
$\lambda=\Theta(\frac{\log\alpha}{\alpha^{2}})$ and
$\varepsilon=\Theta(\frac{\log\alpha}{\alpha})$, with straightforward
calculations we can show that the expected size of the final dominating set is
$(\alpha+O(\log\alpha))\cdot\mathrm{OPT}$ and the algorithm takes
$O(\frac{\alpha}{\log\alpha}\log\Delta)$ many rounds. The bottleneck for the
round complexity is the first phase when we construct $S$ as there the number
of rounds depends linearly on $\frac{1}{\varepsilon}$.

The weighted case is more subtle as there is no bound on the set size. Now
Lemma 4.1 implies that $x_{v}\geq\lambda\tau_{v}$, which is a different value
for every $v$, hence we cannot argue anymore that each node has at most
$\lambda^{-1}$ undominated neighbors. We are not aware of a result in the
literature that we can use as a black box or with a clean reduction for this
case, but we still want to exploit property (b) of Lemma 4.1 to get an
improved approximation. To do so, we devise a simple iterative randomized
algorithm for this case. Towards resolving this, we also improve on the
results of [KW05, KMW06] for solving the dominating set problem on general
graphs. There, they presented a $O(k^{2})$ rounds randomized algorithm with
expected $O(k\Delta^{\frac{2}{k}}\log\Delta)$ approximation factor for the
dominating set problem. We shave off the factor $\log\Delta$ in their bound as
it is stated in Theorem 1.3.

Our algorithm of extending $S$ in full generality is stated in the following
lemma.

######  Lemma 4.6.

For $0<\lambda$ and $1<\gamma$, there is a randomized algorithm that given the
output of Lemma 4.1, it finds $S^{\prime}\subseteq V$ such that $S\cup
S^{\prime}$ is a dominating set and
$\operatorname{\mathbb{E}}[w_{S^{\prime}}]=\gamma(\gamma+1)\lceil\log_{\gamma}\lambda^{-1}\rceil\cdot\mathrm{OPT}$.
The algorithm runs in $O(\log_{\gamma}\lambda^{-1}\log_{\gamma}\Delta)$ rounds
in the $\mathsf{CONGEST}$ model.

By optimizing the parameters in Lemma 4.1 and Lemma 4.6, we can prove the
claim of Theorem 1.2. The theorem is restated below.

See 1.2

###### Proof.

We first execute the algorithm of Lemma 4.1 and then Lemma 4.6 with a suitable
set of parameters such that $w_{S}\leq\alpha(1+\frac{1}{t})$ and
$w_{S^{\prime}}=O(\frac{\alpha}{t})$. Since $S\cup S^{\prime}$ is a dominating
set, this gives us the desired approximation factor. For the parameters, we
set $\varepsilon=\frac{1}{4t}$, $\lambda=\frac{\varepsilon}{\alpha+1}$, and
$\gamma=\max(2,\alpha^{\frac{1}{2t}})$. To bound $w_{S}$, note that:

$\displaystyle w_{S}$
$\displaystyle\leq\alpha(\frac{1}{1+\varepsilon}-\lambda(\alpha+1))^{-1}\cdot\mathrm{OPT}$
$\displaystyle\leq\alpha(1-2\varepsilon)^{-1}\cdot\mathrm{OPT}$
$\displaystyle\leq\alpha(1+4\varepsilon)\cdot\mathrm{OPT}$
$\displaystyle\leq(\alpha+\frac{\alpha}{t})\cdot\mathrm{OPT}$

In the second last inequality, we use the fact that
$\varepsilon=\frac{1}{4t}\leq\frac{1}{4}$. To bound $w_{S^{\prime}}$, first
note that $\lambda^{-1}=4t(\alpha+1)=O(\alpha^{2})$ because
$t\leq\frac{\alpha}{\log\alpha}$. If $\gamma$ is $2$, we have:

$\operatorname{\mathbb{E}}[w_{S^{\prime}}]=O(\gamma^{2}\log_{\gamma}\lambda^{-1}\cdot\mathrm{OPT})=O(\log\alpha)\cdot\mathrm{OPT}=O(\frac{\alpha}{t})\cdot\mathrm{OPT}$

If $\gamma$ is $\alpha^{\frac{1}{2t}}$, then $t\leq\frac{\log\alpha}{2}$, and
we have:

$\operatorname{\mathbb{E}}[w_{S^{\prime}}]=O(\gamma^{2}\log_{\gamma}\lambda^{-1})\cdot\mathrm{OPT}=O(\alpha^{\frac{1}{t}}t)\cdot\mathrm{OPT}=O(\frac{\alpha}{t})\cdot\mathrm{OPT}$

The algorithm of Lemma 4.1 runs in
$O(\frac{\log\Delta}{\varepsilon})=O(t\log\Delta)$ rounds and the algorithm of
Lemma 4.6 runs in

$O(\log_{\gamma}\lambda^{-1}\log_{\gamma}\Delta)=O(\log_{\alpha^{\frac{1}{2t}}}\alpha^{2}\log_{\gamma}\Delta)=O(t\log\Delta)$

rounds. ∎

###### Proof of Lemma 4.6.

We construct $S^{\prime}$ in several steps. For a moment, assume that the
problem is unweighted (all nodes have weight one). From what we have discussed
before, each node can dominate at most $q=O(\alpha)$ nodes in $V\setminus
N^{+}_{S}$. In the first step of constructing $S^{\prime}$, we try to reduce
$q$ to $\frac{q}{2}$. We call a node heavy if it has at least $\frac{q}{2}$
undominated neighbors. To get rid of heavy nodes, first, we sample each of
them with probability $\frac{1}{\Delta+1}$. We add all the sampled nodes to
$S^{\prime}$ and update the set of undominated nodes to $V\setminus
N^{+}_{S\cup S^{\prime}}$. The set of heavy nodes is updated accordingly.
Then, we sample each heavy node with probability $\frac{2}{\Delta+1}$. We
repeat this for $O(\log\Delta)$ iterations until the sampling probability
becomes 1. This ensures that in the end, there is no heavy node. To show that
there are not too many sampled nodes, let $n^{\prime}$ be the number of
undominated nodes before the first iteration and observe that we need at least
$\frac{n^{\prime}}{q}$ nodes to dominate them. It can be shown that after all
the iterations, the expected number of sampled nodes is
$O(\frac{n^{\prime}}{q})$. So in $O(\log\Delta)$ rounds and with an additive
loss of $O(1)$ in the approximation factor, we can reduce $q$ to
$\frac{q}{2}$. Repeating this for $O(\log q)=O(\log\alpha)$ times, we get a
set $S^{\prime}$ in $O(\log\alpha\log\Delta)$ rounds with expected size
$O(\log\alpha\cdot\mathrm{OPT})$ such that $S\cup S^{\prime}$ is a dominating
set. A detailed discussion on the parameterized version of this algorithm that
works also for the weighted case is given in the following.

We start $S^{\prime}$ as an empty set. Unlike the previous parts, for each
node $u$, we set $X_{u}=\sum_{v\in N^{+}_{u}\cap(V\setminus N^{+}_{S\cup
S^{\prime}})}x_{v}$ to be the summation of packing values of only undominated
nodes in $N^{+}_{u}$. Let $\Gamma_{1}=\\{u\not\in S\cup
S^{\prime}:X_{u}\geq\gamma^{-1}w_{u}\\}$. We sample nodes of $\Gamma_{1}$ and
update it for $r=\lceil\log_{\gamma}(\Delta+1)\rceil+1$ iterations. Before the
first iteration, we initialize the sampling probability $p$ with
$\frac{1}{\Delta+1}$. Then, we run the following in each iteration:

  1. 1.

Sample each node in the current $\Gamma_{1}$ with probability $p$.

  2. 2.

Add the sampled nodes to $S^{\prime}$.

  3. 3.

Update $X_{u}$ for each node $u$. That is, compute

$X_{u}=\sum_{v\in N^{+}_{u}\cap(V\setminus N^{+}_{S\cup S^{\prime}})}x_{v}$

.

  4. 4.

Remove all the nodes from $\Gamma_{1}$ with $X_{u}<\gamma^{-1}w_{u}$.

  5. 5.

Set $p\leftarrow\min(\gamma p,1)$.

For each element $v$, we define a random variable $c_{v}$. If $v$ is already
dominated by $S$ or if it is not dominated by $S^{\prime}$ after all the
iterations, we set $c_{v}$ to zero. Otherwise, let $i$ be the first iteration
where $v$ is dominated. We set $c_{v}$ to be the number of sampled nodes in
iteration $i$ that dominates $v$.

######  Lemma 4.7.

For each node $v$, we have
$\operatorname{\mathbb{E}}\left[c_{v}\right]\leq\gamma+1$.

###### Proof.

If $v$ is already dominated by $S$, then $c_{v}$ is always zero. So suppose
this is not the case and assume that it is in $d$ sets of $\Gamma_{1}$ before
the first iteration. Let $d=d_{1}\geq d_{2}\geq\dots\geq d_{r}$ be the
sequence that maximize the expected value of
$\operatorname{\mathbb{E}}[c_{v}]$ where $d_{i}$ is the number of sets in
$\Gamma_{1}$ that contains $v$ in the beginning of iteration $i$. Let
$p_{i}=\frac{\gamma^{i-1}}{\Delta+1}$ be the sampling probablity at iteration
$i$. We have:

$\operatorname{\mathbb{E}}[c_{v}]\leq\sum_{i=1}^{r}p_{i}d_{i}\prod_{j=1}^{i-1}(1-p_{j})^{d_{j}}\leq\sum_{i=1}^{r}p_{i}d_{i}\prod_{j=1}^{i-1}e^{-p_{j}d_{j}}$

To simplify the notation, we define $\beta_{i}=p_{i}d_{i}$. Denote the prefix
sum of sequence $\beta_{i}$ as $\bar{\beta}_{i}=\sum_{j=1}^{i-1}\beta_{i}$.
Let us emphasize that $\bar{\beta}_{i}$ does not include $\beta_{i}$.
Rewriting the above inequality using $\beta$ and $\bar{\beta}$, we have:

$\operatorname{\mathbb{E}}[c_{v}]\leq\sum_{i=1}^{r}\beta_{i}\prod_{j=1}^{i-1}e^{-\beta_{j}}=\sum_{i=1}^{r}\beta_{i}e^{-\bar{\beta}_{i}}$

Since the sequence $d_{1},\dots,d_{r}$ is non-increasing and $p_{i}=\gamma
p_{i-1}$, we have $\beta_{i}\leq\gamma\beta_{i-1}$ for any $2\leq i$. Using
this, we can deduce the following:

$\displaystyle\operatorname{\mathbb{E}}[c_{v}]\leq\sum_{i=1}^{r}\beta_{i}e^{-\bar{\beta}_{i}}$
$\displaystyle=\beta_{1}+\sum_{i=2}^{r}\beta_{i}e^{-\bar{\beta}_{i}}$
$\displaystyle\leq\frac{d_{1}}{\Delta+1}+\sum_{i=2}^{r}\gamma\beta_{i-1}e^{-\bar{\beta}_{i}}$
$\displaystyle\leq
1+\gamma\sum_{i=2}^{r}\int_{\bar{\beta}_{i-1}}^{\bar{\beta}_{i}}e^{-x}dx$

In the last inequality, note that
$\bar{\beta}_{i}-\bar{\beta}_{i-1}=\beta_{i-1}$ by definition. Since all the
integral ranges are disjoint, we have:

$\operatorname{\mathbb{E}}[c_{e}]\leq
1+\gamma\int_{0}^{\infty}e^{-x}dx=\gamma+1$

∎

######  Lemma 4.8.

The expected total weight of sampled nodes in all iterations is at most
$\gamma(\gamma+1)\cdot\mathrm{OPT}$.

###### Proof.

Suppose a node $u$ that is sampled in iteration $i$. Let $T_{u}$ be the set of
nodes in $N^{+}_{u}$ that are undominated in the beginning of iteration $i$.
At that point, $u$ is in $\Gamma_{1}$ implying $\gamma^{-1}w_{u}\leq\sum_{v\in
T_{u}}x_{v}$. So we can upper bound the weight of any sampled node $u$ by
$w_{u}\leq\gamma\sum_{v\in T_{u}}x_{v}$. From the definition of $c_{v}$, each
node $v$ appears in $c_{v}$ many $T_{u}$s for a sampled node $T_{u}$. So the
total weight of sampled nodes is upper bounded by $\gamma\sum_{v\in
V}c_{v}x_{v}$. Finally, we know that
$\operatorname{\mathbb{E}}[c_{v}]\leq\gamma+1$ from Lemma 4.7 which concludes
the proof. ∎

The set $S\cup S^{\prime}$ is not necessarily a dominating set. Consider the
subproblem of dominating $V\setminus N^{+}_{S\cup S^{\prime}}$. Clearly, we
can dominate these nodes with a set of weight at most $\mathrm{OPT}$.
Moreover, $\\{x_{v}\\}_{v\not\in N^{+}_{S\cup S^{\prime}}}$ is a feasible
packing for this subproblem. Multiply the packing value of each node $v\not\in
S\cup S^{\prime}$ by a factor $\gamma$ and update $X_{u}$ for each $u\not\in
S\cup S^{\prime}$. The packing for this subproblem remains feasible. This is
because, in the last iteration, we sample all nodes of $\Gamma_{1}$. So at the
end of this iteration, a node $u$ that is not in $S\cup S^{\prime}$ has
$X_{u}\leq\gamma^{-1}w_{u}$ and as a result, multiplying the packing values by
a factor $\gamma$ is safe.

Now, we define $\Gamma_{2}$ as $\\{u\not\in S\cup
S^{\prime}:X_{u}\geq\gamma^{-1}w_{u}\\}$ and run the procedure with
$\Gamma_{2}$. We repeat this for $t=\lceil\log_{\gamma}\lambda^{-1}\rceil$
times and claim that after that, $S\cup S^{\prime}$ is a dominating set.

Suppose it is not and let $v$ be an undominated node. At the very beginning,
$x_{v}\geq\lambda\tau_{v}$ due to property (b) of Lemma 4.1. Since $v$ is
undominated, its packing value is $\gamma^{i}x_{v}$ after we finish the
process of $\Gamma_{i}$. Since $t=\lceil\log_{\gamma}\lambda^{-1}\rceil$,
there should be an $i$ such that the packing value of $v$ is at least
$\gamma^{-1}\tau_{v}$ when we finish working with $\Gamma_{i-1}$. On the other
hand and from the definition of $\tau_{v}$, there is a neighbor $u$ of $v$
with weight $\tau_{v}$. This means that $u$ is in $\Gamma_{i}$ and it remains
in $\Gamma_{i}$ until it is sampled. This contradicts that $v$ is not
dominated.

From Lemma 4.8, the expected weight of the sampled nodes in one phase is
$\gamma(\gamma+1)\cdot\mathrm{OPT}$. So in total, the expected weight of
$S^{\prime}$ is
$\gamma(\gamma+1)\lceil\log_{\gamma}\lambda^{-1}\rceil\cdot\mathrm{OPT}$.

Each iteration of each phase can be run in $O(1)$ rounds in the
$\mathsf{CONGEST}$ model. So in total, the algorithm needs

$O(t\cdot r)=O(\log_{\gamma}\lambda^{-1}\log_{\gamma}\Delta)$

many rounds. ∎

See 1.3

###### Proof.

In Lemma 4.6, we assume $S$ is empty and set $\lambda$ to
$\frac{1}{\Delta+1}$. This does not violate any condition in the lemma. By
setting $\gamma$ to $\Delta^{\frac{1}{k}}$, the output $S^{\prime}$ of the
lemma is a dominating set with the claimed size. ∎

##  5 Lower Bound

See 1.4

###### Proof.

Kuhn, Moscibroda and Wattenhofer proved that obtaining a constant or poly-
logarithmic approximation for the Minimum Vertex Cover (MVC) problem requires
$\Omega\left(\frac{\log\Delta}{\log\log\Delta}\right)$ rounds in the
$\mathsf{LOCAL}$ model [KMW16]. In fact, their lower bound holds even for the
_fractional_ version of the problem, in which the goal is to assign a value
$x_{v}$ for each node such that for each edge $\\{u,v\\}\in E$, we have that
$x_{v}+x_{u}\geq 1$, and $\sum_{v}x_{v}$ is minimized. Let $G$ be the Kuhn-
Moscibroda-Wattenhofer (KMW) lower bound graph for approximating the Minimum
Fractional Vertex Cover ($\mathrm{MFVC}$), with maximum degree $\Delta$, $n$
nodes, and $m$ edges. We build a new graph $H$ as follows: Take $\Delta^{2}$
copies of $G$, let us call them $G_{1}$, $G_{2}$, $\ldots$, $G_{\Delta^{2}}$.
Add a set $T$ of $n$ additional nodes, one for each node of $G$, and connect
each new node to all copies of that original $G$-node. So the degree of each
node in $T$ is $\Delta^{2}$. Next, for each $G_{i}$, add a node in the middle
of each of its edges. This completes the construction of $H$. See Fig. 1 for
an illustration. Some observations on $H$ is in the following:

  * -

Each $G_{i}$ has $n+m$ nodes (one copy for each node of $G$ and $m$ middle
nodes) and $2m$ edges. Taking $T$ into consideration, $H$ has
$\Delta^{2}(n+m)+n$ nodes and $\Delta^{2}(2m+n)$ edges.

  * -

The maximum degree of $H$ is $\Delta^{2}$.

  * -

The arboricity of $H$ is 2. For each middle node, orient its two incident
edges outward. For each node in $T$, orient its $\Delta^{2}$ incident edges
inward. This gives us an orientation of all the edges of $H$. There is no
directed cycle in this orientation and its maximum out-degree is $2$, so the
arboricity of $H$ is $2$.

  * -

Let $\mathrm{OPT}_{\mathrm{MDS}}^{H}$ be the size of the minimum dominating
set of $H$ and $\mathrm{OPT}_{\mathrm{MVC}}^{G}$
($\mathrm{OPT}_{\mathrm{MFVC}}^{G}$) be the size of the minimum (fractional)
vertex cover of $G$, then:

$\mathrm{OPT}_{\mathrm{MDS}}^{H}\leq\Delta^{2}\cdot\mathrm{OPT}^{G}_{\mathrm{MVC}}+n=\Delta^{2}\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}+n$
(2)

The first inequality is because $T$ along with copies of a minimum vertex
cover of $G$ in each $G_{i}$ is a dominating set of $H$. This is because every
node in $G_{i}$ that is not a middle-node has a neighbor in $T$. On the other
hand, all the middle-nodes are dominated as we add a vertex cover for each
$G_{i}$. For the equality
$\mathrm{OPT}^{G}_{\mathrm{MVC}}=\mathrm{OPT}^{G}_{\mathrm{MFVC}}$ in (2), we
leverage the fact that the KMW graph $G$ is bipartite and as a result the
integrality gap of vertex cover on $G$ is 1.333Alternatively, we can use the
fact that $\mathrm{OPT}^{G}_{\mathrm{MVC}}\leq
2\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}$ in any graph, which would only change
the constant in our analysis. In addition,
$\mathrm{OPT}^{G}_{\mathrm{MFVC}}\geq\frac{m}{\Delta}$. This holds as if
$\\{x_{v}\\}_{v}$ is the optimal fractional solution, we have that

$m\leq\sum_{\\{u,v\\}\in
E}(x_{u}+x_{v})\leq\Delta\sum_{v}x_{v}=\Delta\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}.$

Since $\mathrm{OPT}^{G}_{\mathrm{MFVC}}\geq\frac{m}{\Delta}$ and for the KMW
graph we have $m\geq n$, we can write:

$\mathrm{OPT}_{\mathrm{MDS}}^{H}\leq(\Delta^{2}+\Delta)\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}.$

Figure 1: The lower bound graph $H$ assumes that the KMW graph $G$ is $K_{4}$.
Only three copies (rather than nine copies) of $G$ are drawn. The middle nodes
are indicated by hollow diamonds and $T$ is the set of four nodes in the gray
area.

To prove the theorem, suppose there is an algorithm $\mathcal{A}$ with round
complexity $o\left(\frac{\log\Delta}{\log\log\Delta}\right)$ that computes a
$c$-approximation of Minimum Dominating Set ($\mathrm{MDS}$) on $H$ for some
constant or poly-logarithmic $c$. Using this algorithm, we will show that we
get an algorithm that computes a $c(1+\frac{1}{\Delta})$ approximation of
$\mathrm{MFVC}$ of $G$ in the same number of rounds, hence putting us in
contradiction with the lower bound of [KMW16], thus completing the proof.

Notice that the graph $G$ can simulate the graph $H$ in the $\mathsf{LOCAL}$
model, where each node simulates all its copies in $H$, and each node in $H$
that corresponds to an edge in $G$ is simulated by one of its endpoints. Note
that for each edge in $H$, its two endpoints are simulated either by the same
node in $G$ or by two neighboring nodes in $G$, hence we can simulate a round
of an algorithm in $H$ in one round in $G$. Let us run the algorithm on the
graph $H$, by actually working on the graph $G$. Let $S$ be the computed
dominated set of $H$. We want to turn $S$ into a fractional vertex cover of
$G$. First, replace each middle node in $S$ with one of its endpoints. This
can only decrease the size of $S$ and after it, all the middle nodes are still
dominated. Let $S_{i}$ be the set of nodes of $G_{i}$ in $S$. Since $S$
dominates all the middle nodes, $S_{i}$ is a vertex cover of the original
graph $G$. As $\mathcal{A}$ is a $c$-approximation algorithm for MDS, we have:

$\sum_{i\in[\Delta^{2}]}|S_{i}|\leq|S|\leq
c(\Delta^{2}+\Delta)\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}$

At the end, each node $v$ of $G$, computes $y_{v}=\frac{|\\{i:v\in
S_{i}\\}|}{\Delta^{2}}$. Observe that $\sum_{v}y_{v}\leq
c(1+\frac{1}{\Delta})\cdot\mathrm{OPT}^{G}_{\mathrm{MFVC}}$, and we show that
$\\{y_{v}\\}_{v}$ is a fractional vertex cover of $G$. This follows from the
fact that each $S_{i}$ is a vertex cover of $G$. Hence, for each edge
$\\{u,v\\}\in G$, if we denote by $\\{u_{i},v_{i}\\}$ the corresponding edge
in $G_{i}$, we have that at least one of $u_{i},v_{i}$ is in the vertex cover.
Let $y^{i}_{v}$ indicate if $v_{i}\in S_{i}$. We have

$y_{u}+y_{v}=\frac{1}{\Delta^{2}}\sum_{1\leq
i\leq\Delta^{2}}(y^{i}_{u}+y^{i}_{v})\geq 1,$

as needed. So if $\mathcal{A}$ exists, then we can compute a
$c(1+\frac{1}{\Delta})$ approximation of minimum fractional vertex cover of
$G$ in $o\left(\frac{\log\Delta}{\log\log\Delta}\right)$ rounds contradicting
the lower bound of [KMW16]. ∎

## Acknowledgments

This work was supported in part by funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No. 853109), and the Swiss National Foundation
(project grant 200021-184735).

## References

  * [AAOdMRS18] Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz.  Distributed domination on graph classes of bounded expansion.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 143–151, 2018.
  * [Ami21] Saeed Akhoondian Amiri.  Deterministic CONGEST algorithm for MDS on bounded arboricity graphs.  CoRR, abs/2102.08076, 2021.
  * [ASS19] Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz.  Distributed dominating set approximations beyond planar graphs.  ACM Transactions on Algorithms (TALG), 15(3):1–18, 2019.
  * [BCGW21] Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek.  A tight local algorithm for the minimum dominating set problem in outerplanar graphs.  In 35th International Symposium on Distributed Computing, DISC 2021, volume 209 of LIPIcs, pages 13:1–13:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [BE10] Leonid Barenboim and Michael Elkin.  Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition.  Distributed Computing, 22(5):363–379, 2010.
  * [BU17] Nikhil Bansal and Seeun William Umboh.  Tight approximation bounds for dominating set on graphs of bounded arboricity.  Information Processing Letters, 122:21–24, 2017.
  * [CCMU21] Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto.  Massively parallel correlation clustering in bounded arboricity graphs.  In 35th International Symposium on Distributed Computing, DISC 2021, volume 209 of LIPIcs, pages 15:1–15:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [CHW08] Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak.  Fast distributed approximations in planar graphs.  In International Symposium on Distributed Computing, pages 78–92. Springer, 2008.
  * [DKM19] Janosch Deurer, Fabian Kuhn, and Yannic Maus.  Deterministic distributed dominating set approximation in the congest model.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 94–103, 2019.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624–633, 2014.
  * [Dvo19] Zdeněk Dvořák.  On distance-dominating and-independent sets in sparse graphs.  Journal of Graph Theory, 91(2):162–173, 2019.
  * [ELR20] Talya Eden, Reut Levi, and Dana Ron.  Testing bounded arboricity.  ACM Transactions on Algorithms (TALG), 16(2):1–22, 2020.
  * [GBSH21] Lukas Gianinazzi, Maciej Besta, Yannick Schaffner, and Torsten Hoefler.  Parallel algorithms for finding large cliques in sparse graphs.  In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 243–253, 2021.
  * [GG06] Gaurav Goel and Jens Gustedt.  Bounded arboricity to determine the local structure of sparse graphs.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 159–167. Springer, 2006.
  * [GKM17] M. Ghaffari, F. Kuhn, and Y. Maus.  On the complexity of local distributed graph problems.  In Proc. 49th ACM Symp. on Theory of Computing (STOC), pages 784–797, 2017.
  * [Joh74] David S Johnson.  Approximation algorithms for combinatorial problems.  Journal of computer and system sciences, 9(3):256–278, 1974.
  * [JRS02] Lujun Jia, Rajmohan Rajaraman, and Torsten Suel.  An efficient distributed algorithm for constructing small dominating sets.  Distributed Computing, 15(4):193–205, 2002.
  * [KMW06] F. Kuhn, T. Moscibroda, and R. Wattenhofer.  The price of being near-sighted.  In Proc. 17th Symp. on Discrete Algorithms (SODA), pages 980–989, 2006.
  * [KMW16] F. Kuhn, T. Moscibroda, and R. Wattenhofer.  Local computation: Lower and upper bounds.  Journal of the ACM, 63(2), 2016.
  * [KW05] Fabian Kuhn and Roger Wattenhofer.  Constant-time distributed dominating set approximation.  Distributed Computing, 17(4):303–310, 2005.
  * [LOW08] Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer.  What can be approximated locally? case study: Dominating sets in planar graphs.  In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA), pages 46–54, 2008.
  * [LPW13] Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.  Distributed minimum dominating set approximations in restricted families of graphs.  Distributed computing, 26(2):119–137, 2013.
  * [LW10] Christoph Lenzen and Roger Wattenhofer.  Minimum dominating set approximation in graphs of bounded arboricity.  In International symposium on distributed computing (DISC), pages 510–524. Springer, 2010.
  * [MSW21] Adir Morgan, Shay Solomon, and Nicole Wein.  Algorithms for the minimum dominating set problem in bounded arboricity graphs: Simpler, faster, and combinatorial.  In 35th International Symposium on Distributed Computing, DISC 2021, volume 209 of LIPIcs, pages 33:1–33:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [RG20] V. Rozhoň and M. Ghaffari.  Polylogarithmic-time deterministic network decomposition and distributed derandomization.  In Proc. 52nd ACM Symp. on Theory of Computing (STOC), pages 350–363, 2020.
  * [Sun21] Hao Sun.  An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity.  In International Workshop on Approximation and Online Algorithms, pages 39–47. Springer, 2021.
  * [Waw14] Wojciech Wawrzyniak.  A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs.  Information Processing Letters, 114(3):94–98, 2014.

##  Appendix A Missing Proofs

######  Observation A.1.

There is a single-round algorithm that computes a $3$-approximation of minimum
unweighted dominating set on graphs of arboricity $1$.

###### Proof.

Take all non-leaf nodes as the dominating set. This is a dominating set, we
next show the approximation ratio. Let $S^{*}$ be an optimal dominating set. A
graph of arboricity 1 is a forest, we can fix a root in each one of the trees.
We create a dominating set $S^{\prime}$ as follows. For each node $v\in
S^{*}$, we add to $S^{\prime}$ the node $v$ along with its parent and
grandparent in the tree (if they exist). Clearly $|S^{\prime}|\leq 3|S^{*}|$.
We show that $S^{\prime}$ contains all non-leaf nodes, completing our proof.
Assume to the contrary that there is a node $v\not\in S^{\prime}$ that is an
internal node in the tree, and let $u$ be a child of $v$ (that exists, as $v$
is non-leaf). It follows that $u\not\in S^{*}$, as otherwise $v\in
S^{\prime}$. Since $v$ and $u$ are not in $S^{*}$, and $S^{*}$ is a dominating
set, there is a child $w$ of $u$ such that $w\in S^{*}$, but then $v\in
S^{\prime}$, a contradiction. ∎