# On Distributed Algorithms for Minimum Dominating Set problem, from theory to
application

Sharareh Alipour  Institute for research in fundamental sciences(IPM)P.O. Box
1212TehranIran<EMAIL_ADDRESS>,  Ehsan Futuhi  Amirkabir universityTehranIran
<EMAIL_ADDRESS>and  Shayan Karimi  Amirkabir universityTehranIran
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we propose a distributed algorithm for the minimum dominating
set problem. For some especial networks, we prove theoretically that the
achieved answer by our proposed algorithm is a constant approximation factor
of the exact answer. This problem arises naturally in social networks, for
example in news spreading, avoiding rumor spreading and recommendation
spreading. So we implement our algorithm on massive social networks and
compare our results with the state of the art algorithms. Also, we extend our
algorithm to solve the $k$-distance dominating set problem and experimentally
study the efficiency of the proposed algorithm.

Our proposed algorithm is fast and easy to implement and can be used in
dynamic networks where the edges and vertices are added or deleted constantly.
More importantly, based on the experimental results the proposed algorithm has
reasonable solutions and running time which enables us to use it in
distributed model practically.

PVLDB Reference Format:
PVLDB, 14(1): XXX-XXX, 2020.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttp://vldb.org/pvldb/format_vol14.html.

##  1\. Introduction

Nowadays online social networks are growing exponentially and they have
important effect on our daily life. They influence politics and economics.
Online shopping, online advertisement and social medias have important role in
our life style. Even we communicate more with friends and family on social
networks than face to face meetings.

To influence the network participants a key feature in a social network is the
ability to communicate quickly within the network. For example, in an
emergency situation, we may need to be able to reach to all network nodes, but
only a small number of individuals in the network can be contacted directly
due to the time or other constraints. However, if all nodes from the network
are connected to at least one such individual who can be contacted directly
(or is one of those individuals) then the emergency message can be quickly
sent to all network participants. Or suppose that in a social network some
nodes should be selected to distribute a news in the network or should be
selected to avoid spreading rumors by checking the spreading news in the
network. In these scenarios the goal is to choose the minimum number of such
nodes. In graph theory this problem is called minimum dominating set problem.

Given a graph $G=(V,E)$ with the vertex set $V$ and the edge set $E$, a subset
$S\subseteq V$ is a dominating set for $G$ if each node $v\in V\backslash S$
has a neighbor in $S$. Also $S\subseteq V$ is a total dominating set of $G$ if
each node $v\in V$ has a neighbor in $S$. Let $\gamma(G)$ and $\gamma_{t}(G)$
be the size of a minimum dominating set (MDS) and a minimum total dominating
set (MTDS) for a graph $G$, respectively. It is easy to see that if $G$ has no
isolated vertices then $\gamma(G)\leq\gamma_{t}(G)\leq 2\gamma(G)$. Dominating
set is an important concept in graph theory which arises in many areas. When
the given network is very large such as social networks, we have limitations
in memory and time. Sometimes we need to run the algorithm on distributed
model. In a distributed model the network is abstracted as a simple $n$-node
undirected graph $G=(V,E)$. There is one processor on each graph node $v\in
V$, with a unique $\Theta(logn)$-bit identifier $ID(v)$, who initially knows
only its neighbors in $G$. Communication happens in synchronous rounds. Per
round, each node can send one, possibly different, $O(\log n)$-bit message to
each of its neighbors. At the end, each node should know its own part of the
output. For instance, when computing the dominating set, each node knows
whether it is in the dominating set or has a neighbor in the dominating set.

An extension of minimum dominating set problem is minimum $k$-distance
dominating set problem where the goal is to choose a subset $S\subseteq V$
with minimum cardinality such that for every vertex $v\in V\backslash S$,
there is a vertex $u\in S$ such that there is a path between them of length at
most $k$. The minimum total $k$-distance dominating set is defined similarly.
In social networks the minimum $k$-distance dominating set can be considered
as social recommenders. The close nodes influence each other and they have the
same preferences in a network. Suppose that we want to give a recommendation
on a special product (e.g. which movie to watch) to each node of the network
but we can not reach all of them because of the time constraint and
advertising cost. We may choose minimum number of nodes such that they
dominate all other nodes within distance $k$ from them. We give a
recommendation to each of the selected nodes and then they spread it in the
network. This is equal to solving the $k$-distance dominating set problem. For
more on social recommendation see (Gulati and Eirinaki, 2019).

###  1.1. Previous works

Finding a minimum dominating set is NP-complete (Karp, 1972), even for planar
graphs of maximum degree $3$ (Garey and Johnson, 1979), and cannot be
approximated for general graphs with a constant ratio under the assumption
$P\neq NP$ (Raz and Safra, 1997). An $O(logn)$-approximation factor can be
found by using a simple greedy algorithm. Moreover, negative results have been
proved for the approximation of MDS even when limited to the power law graphs
(Gast et al., 2015).

A number of works have been done on exact algorithms for MDS, which mainly
focus on improving the upper bound of running time. State of the art exact
algorithms for MDS are based on the branch and reduce paradigm and can achieve
a run time of $O({1.4969}^{n})$ (van Rooij and Bodlaender, 2011). Fixed
parameterized algorithms have allowed to obtain better complexity results
(Karthik C. S. et al., 2018). The main focus of such algorithms is on
theoretical aspects. In the distributed model it is known that finding small
dominating sets in local model is hard. Kuhn and Wattenhofer (Kuhn et al.,
2016) proposed an algorithm with an approximation factor that is a function of
the number of communication rounds. And the number of communication rounds
also depends on $\Delta$. For more theoretical results on distributed
algorithms for MDS problem see (Amiri et al., 2019). In (Hilke et al., 2014)
it has been shown that for any $\epsilon>0$ there is no deterministic local
algorithm that finds a $(7-\epsilon)$\- approximation of a minimum dominating
set for planar graphs. However, there exist an algorithm with approximation
factor of $52$ for computing a MDS in planar graphs (Czygrinow et al., 2008;
Lenzen et al., 2013) in local model and an algorithm with approximation factor
of $636$ for anonymous networks (Czygrinow et al., 2008; Wawrzyniak, 2013). In
(Alipour and Jafari, 2020), they improved the approximation factor in
anonymous networks to $18$ in planar graphs without $4$-cycles. For more
information on local algorithms see (Suomela, 2013).

In practice, these theoretical algorithms are not applicable specially in
large social networks because of time and space constraints. So we need to use
heuristic algorithms to obtain solutions. See (Sanchis, 2002) for a comparison
among several greedy heuristics for MDS. Heuristic search methods such as
genetic algorithm (Hedar and Ismail, 2010) and ant colony optimization
(Potluri and Singh, 2011, 2013) have been developed to solve MDS. Also Hyper
metaheuristic algorithms combine different heuristic search algorithms and
preprocessing techniques to obtain better performance (Potluri and Singh,
2013; Chaurasia and Singh, 2015; Bouamama and Blum, 2016; Lin et al., 2016;
Abu-Khzam et al., 2017). These algorithms were tested on standard benchmarks
with up to thousand vertices. The configuration checking (CC) strategy (Cai et
al., 2011) has been applied to MDS and led to two local search algorithms.
Wang et al. proposed the CC2FS algorithm for both unweighted and weighted MDS
(Wang et al., 2017), and obtained better solutions than ACO-PP-LS (Potluri and
Singh, 2013) on standard benchmarks. Afterwards, another CC-based local search
named FastMWDS was proposed, which significantly improved CC2FS on weighted
massive graphs (Wang et al., 2018). Chalupa proposed an order-based randomized
local search named RLSo (Chalupa, 2018), and achieved better results than ACO-
LS and ACO-PP-LS (Potluri and Singh, 2011, 2013) on standard benchmarks of
unit disk graphs as well as some massive graphs. Fan et. al. designed a local
search algorithm named ScBppw (Fan et al., 2019), based on two ideas including
score checking and probabilistic random walk. Recently an efficient local
search algorithm for MDS is proposed in (Cai et al., 2020). The algorithm
named FastDS is evaluated on some standard benchmarks. FastDS obtains the best
performance for almost all benchmarks, and obtains better solutions than
previous algorithms on massive graphs in their experiments.

A recent study for the $k$-distance dominating set problem can be found in
(Nguyen et al., 2020). They proposed a heuristic algorithm that can handle
real-world instances with up to $17$ million vertices and $33$ million edges.
They stated that this is the first time such large graphs are solved for the
minimum $k$-distance dominating set problem. They compared their proposed
algorithm with the other best know algorithms for this problem.

###  1.2. Our results

In this paper we propose a local approximation algorithm which is an extension
of (Alipour and Jafari, 2020). We prove that the approximation factor of this
algorithm in planar triangle free graphs is $16$ and $32$ for MTDS problem and
MDS problem, respectively.

We implement the centralized version of our algorithm and run it on real
massive networks. The proposed algorithm is fast and easy to implement both in
distributed model and centralized model and the achieved results are
satisfactory. Also the proposed algorithm can be used in dynamic networks,
where the network is changing constantly i.e. during the time some nodes and
edges are added or deleted. For example in a social network some users may be
offline during a time period and so they are disconnected from the network and
this affects the network. We compare the results of centralized version of our
algorithm with the results of (Cai et al., 2020) to show the efficiency of the
achieved results. Also since the algorithm is fast, we compute dominating set
for the other massive graphs. For further experiments we modify the algorithm
to solve the $k$-distance dominating set problem and compare the results with
(Nguyen et al., 2020).

Note that our main goal is to show the efficiency of proposed algorithm in
distributed model and the experimental results show that the algorithm can be
used in practice for large networks.

##  2\. LOCAL algorithm for dominating set in graphs

In this section we present our local algorithm for computing a (total)
dominating set in graphs. We also compute the approximation factor of the
algorithm, Algorithm 1, for triangle free planar graphs.

###  2.1. Algorithm

Let $G$ be a graph with vertex set $V=\\{v_{1},\dots,v_{n}\\}$ and let $d_{i}$
be the degree of $v_{i}$. A local distributed algorithm that computes a total
dominating set for $G$ is presented in Algorithm 1. We assume that $G$ does
not have isolated vertices (vertices with degree $0$) because the concept of
total dominating set can not be defined if the graph has a vertex with degree
$0$.

1: In the first round, each node $v_{i}$ chooses a random number $0<r_{i}<1$
and computes its weight $w_{i}=d_{i}+r_{i}$ and sends $w_{i}$ to its adjacent
neighbors.

2: In the second round, each node $v$ marks a neighbor vertex $v_{i}$, whose
weight $w_{i}$ is maximum among all the other neighbors of $v$.

3: for $m$ rounds do

4: Let $x_{i}$ be the number of times that a vertex is marked by its neighbor
vertices, let $w_{i}=x_{i}+r_{i}$

5: Unmark the marked vertices.

6: Each vertex marks the vertex with maximum $w_{i}$ among its neighbor
vertices.

7: end for

8: The marked vertices are considered as the vertices in our total dominating
set for $G$.

Algorithm 1 Distributed Algorithm for computing a total dominating set in a
graph with given integer $m\geq 0$.

Now we show the correctness of Algorithm 1. In each step each vertex marks one
of its adjacent vertices, this means the marked vertices form a total
dominating set. Note that a total dominating set is also a dominating set so,
this algorithm also serves as an algorithm for MDS problem.

###  2.2. Approximation factor of Algorithm 1 for $m=0$ in planar graphs
without triangles

Now we compute the approximation factor of Algorithm 1 for planar triangle
free graphs.

###### Theorem 2.1.

The approximation factor of Algorithm 1 with $m=0$ for triangle free planar
graphs for MDS problem and MTDS problem are respectively $32$ and $16$.

###### Proof.

Let $V^{\prime}=\\{v^{\prime}_{1},v^{\prime}_{2},\dots,v^{\prime}_{k}\\}$ be
the set of vertices that are marked in the algorithm. Let
$V_{opt}=\\{v^{*}_{1},\dots,v^{*}_{opt}\\}$ be an optimal solution for MTDS.
We construct a planar multi-graph $G^{\prime}$ (i.e. might have multiple edges
between two of its vertices) with the vertex set of $V_{opt}$ and $k$ edges
that are traced either along an edge of $G$ or along a path of length $3$ of
$G$ (called a broken edge). We show that each edge of this graph is counted at
most twice, so we have a planar graph with at least $k/2$ edges. Since this
graph is planar, we can divide the edges between two vertices (if there are
many) into two groups, the top and bottom edges (called outer edges), and the
middle edges (called inner edges). We can at most have $6opt$ outer edges
(planar simple graph with $m$ vertices has at most $3m$ edges. Our graph might
have double edges, hence the factor of $6$). To any inner edge we associate a
vertex $z^{*}$ in $V_{opt}$ and show that each element of $V_{opt}$ can be
associated to at most $2$ inner edges and hence the number of inner edges is
at most $2opt$. So $k/2$ is at most $6opt+2opt=8opt$ and $k<16opt$. Now we
explain the details.

To any vertex $v$ associate in an arbitrary way a vertex $v^{*}\in V_{opt}$
that dominates it. For each $v^{\prime}\in V^{\prime}$, choose a vertex $u$
that marks it. Now let $v^{*}$ and $u^{*}$ be the dominating vertices in
$V_{opt}$ for $v^{\prime}$ and $u$. Since $G$ is triangle free, so $v^{*}\neq
u^{*}$ . If $u^{*}$ and $v^{*}$ are different from $v^{\prime}$ and $u$ then
we draw a broken edge traced on the path of length three
$u^{*}-u-v^{\prime}-v^{*}$ otherwise they are connected by an edge $e$ in $G$
that we trace $e$ (tracing means we draw an edge almost identical, so we avoid
unnecessary collision of edges). For each element of $V^{\prime}$ we have an
edge between two vertices of $V_{opt}$ so we have $k$ edges. The broken edge
$u^{*}-u-v^{\prime}-v^{*}$ will be counted twice if $u$ is also in
$V^{\prime}$ and $v^{\prime}$ is the vertex that marks it. There is no
crossing, since a crossing can occur either at the vertex $u$ or $v^{\prime}$,
when $u$ is in $V^{\prime}$ or $v^{\prime}$ marks a vertex $v^{\prime\prime}$
in $V^{\prime}$. In both cases since we have chosen a fixed dominating vertex
in $V_{opt}$, we can draw the broken edge in a non-crossing manner. If
$v^{*}-x-y-w^{*}$ is an inner edge and $x$ has marked $y$, since $d_{v^{*}}$
is at least $3$ (there are two outer edges in this case) so $d_{y}$ is at
least $3$ as well, and hence there is a vertex $z$ that is connected to $y$
and hence there is a vertex $z^{*}$ in $V_{opt}$ that dominates it. We
associate $z^{*}$ to this inner edge. Since $z^{*}$ is bounded between two
(broken) edges from $v^{*}$ to $w^{*}$ it can be associated to at most one
more inner edge, therefore the number of inner edges is at most $2opt$.

∎

Note that $r_{i}$’s are not used in this proof, however in experiments they
give a total order on the vertices of the graph (according to
$d_{v_{i}}+r_{i}$) and hence the number of marked vertices will be reduced in
principle. For example consider a complete graph (although non-planar) without
$r_{i}$’s then it is possible that each vertex chooses a different neighbor
and instead of just one vertex, all the vertices get marked. But with
$r_{i}$’s all the vertices will choose one vertex.

Now we show how to extend this algorithm to solve the $k$-distance dominating
set problem. In solving the $k$-distance dominating set problem, for each node
$v$, its neighbors are the vertices that their distance from $v$ is at most
$k$ and the algorithm is run as before.

##  3\. Experimental results

In this section we present our experimental results. In theory we have seen
that the algorithm has good approximation factor in certain networks, for
example planar graphs without 4-cycles or planar graphs without triangles.
These approximation factors are achieved in the worst case, however in
practice this is not the case that happens most of the time. So based on this
fact we can expect good results for real data too.

We choose $5$ benchmarks which were used in (Cai et al., 2020) to compare the
performance of our algorithms with their algorithm which is denoted as FastDS.
In (Cai et al., 2020) they compared FastDS with four heuristic algorithms,
including CC2FS (Wang et al., 2017), FastMWDS (Wang et al., 2018), RLS
(Chalupa, 2018) and ScBppw (Fan et al., 2019). It is stated that CC2FS is good
at solving standard benchmarks, while FastMWDS and ScBppw are designed to
solve massive graphs, and RLSo is a recent algorithm that outperforms previous
ant optimization and hyper meta-heuristic algorithms.

In (Cai et al., 2020) for each instance, all algorithms were executed $10$
times with random seeds $1,2,3\dots 10$. The time limit of each run was $1000$
seconds. For each instance, they reported the best size (Dmin) and the average
size (Davg) of the solutions found over the $10$ runs. Compared to the other
algorithms the FastDS algorithm outperformed in the quality of solutions in
most cases (Cai et al., 2020).

In the following we present a brief description of the benchmarks from (Cai et
al., 2020).

T1111http://mail.ipb.ac.rs/ rakaj/home/BenchmarkMWDSP.htm: This data set
consists of $520$ instances where each instance has two different weight
functions. As in (Cai et al., 2020) we select these original graphs where the
weight of each vertex is set to $1$. There are $52$ families, each of which
contains $10$ instances with the same size.

BHOSLIB222http://networkrepository.com/bhoslib.php: This benchmark are
generated based on the RB model near the phase transition. It is known as a
popular benchmark for graph theoretic problems.

SNAP333http://snap.stanford.edu/data: This benchmark is from Stanford Large
Network Dataset Collection. It is a collection of real world graphs from
$10^{4}$ vertices to $10^{7}$ vertices.

DIMACS10444http://networkrepository.com/dimacs10.php: This benchmark is from
the 10th DIMACS implementation challenge, which aims to provide large
challenging instances for graph theoretic problems.

Network Repository555http://networkrepository.com/: The Network Data
Repository includes massive graphs from various areas. Many of the graphs have
$100$ thousands or millions of vertices. This benchmark has been widely used
for graph theoretic problems including vertex cover, clique, coloring, and
dominating set problems.

As in (Cai et al., 2020) for SNAP benchmarks we consider the graphs with at
list $30000$ vertices and for Repository benchmark we choose the graphs with
at least $10^{5}$ vertices.

In (Cai et al., 2020) the algorithms were implemented in C++ and complied by
g++. All experiments were run on a server with Intel Xeon E5-2640 v4 2.40GHz
with 128GB RAM under CentOS 7.5. In our experiment the algorithm is
implemented in Java and is run on a server with Intel Xeon E5-2650 v3s 2.29GHz
with 70GB RAM under Ubuntu 18.04.4.

In Table 1 the average running time of Algorithm 1, FastDS, CCFS and FastMWDS
for BHOSLIB and T1 benchmarks are stated. Note that we can not compare the
running times because the configuration of our system and the programming
language in our experiments are not the same as (Cai et al., 2020) but we
remark that their’s is more efficient than ours.

As it can be seen for these benchmarks our algorithm is really fast. In all
our experiments we mention the running time for each instance in our
sequential implementations.

Table 1. Average running time of algorithms. Benchmark | CCFS | FastMWDS | FastDs | Algorithm 1 $m=0,2,5$
---|---|---|---|---
T1 | 4.88s | 8.35s | 11.23s | 0.0021, 0.0048, 0.0074
BHOSLIB | 96.68s | 101.44s | 95.62s | 0.028, 0.076, 0.111

In the following, we presented our experimental results. Note that our
algorithm computes a total dominating set and since a total dominating set is
also a dominating set, we report the marked vertices as a dominating set. In
theory, the MTDS is at most $2$ times of MDS, so this explains why our answers
are greater than the answers of FastDS algorithm. Also, note that we can have
a trade-off between the running time and the quality of solution by changing
the value of $m$. However our experiments show that the quality of solution
does not have significant improvement for large values of $m$. By experiment
we have chosen the value of $m$ to be $0$, $2$ and $5$.

Table 2 contains the results for T1 benchmark. In Table 3 we present the
results for BHOSLIB benchmark. In this benchmark the achieved results by
Algorithm 1 are surprisingly better than FastDs. This happens because of the
nature of our algorithm. In dense graphs or the graphs with large maximum
degree, close to $n$ (number of vertices), the adjacent vertices to the
maximum degree choose it, so the number of marked vertices is small and close
to the exact solution. For example in frb100-40 instance of BHSLIB benchmark,
the number of vertices is about 4000, the maximum degree is 3864, the minimum
degree is 3553. Our algorithm choose $3$ vertices, v1096, v1555 and v1088 with
degrees $3864$, $3861$ and $3861$ respectively.

Table 4 contains the result for snap and DIMACS10 benchmarks. In Table 5 we
present the result for Network repository benchmark. In this benchmark we also
run the algorithm on more instances related to web and social networks other
than (Cai et al., 2020). The empty cells are the instances that were not
computed in (Cai et al., 2020).

Table 2. Experimental results for T1 benchmark for $m=0,2,5$. instance | time(s) $m=0,2,5$ | Sol Alg 1 | FastDS (Cai et al., 2020)
---|---|---|---
V100E100 | 0.001, 0.002, 0.004 | 66, 65, 63 | 33.6
V100E1000 | 0.000, 0.000, 0.001 | 14, 12, 12 | 7.5
V100E2000 | 0.000, 0.000, 0.001 | 6, 6, 6 | 4.1
V100E250 | 0.000, 0.001, 0.003 | 39, 33, 31 | 19.9
V100E500 | 0.001, 0.002, 0.005 | 22, 19, 20 | 12.2
V100E750 | 0.001, 0.003, 0.005 | 14, 14, 12 | 9
V150E1000 | 0.001, 0.001, 0.001 | 25, 22, 22 | 15
V150E150 | 0.001, 0.003, 0.003 | 100, 97, 96 | 50
V150E2000 | 0.000, 0.001, 0.004 | 16, 15, 14 | 9
V150E250 | 0.001, 0.002, 0.012 | 66, 63, 61 | 39.1
V150E3000 | 0.001, 0.001, 0.005 | 14, 13, 11 | 6.9
V150E500 | 0.000, 0.005, 0.006 | 39, 37, 36 | 24.6
V150E750 | 0.000, 0.001, 0.002 | 34, 27, 26 | 18.3
V200E1000 | 0.000, 0.001, 0.003 | 44, 36, 35 | 24.4
V200E2000 | 0.000, 0.001, 0.002 | 26, 22, 22 | 15
V200E250 | 0.001, 0.002, 0.003 | 102, 99, 97 | 61.1
V200E3000 | 0.001, 0.001, 0.002 | 21,16,15 | 11
V200E500 | 0.000, 0.001, 0.005 | 65,61,60 | 36.6
V200E750 | 0.001, 0.001, 0.002 | 54,47,45 | 30
V250E1000 | 0.001, 0.001, 0.003 | 61,54,52 | 36
V250E2000 | 0.000, 0.001, 0.002 | 38, 31, 31 | 21.6
V250E250 | 0.002, 0.002, 0.004 | 164, 160, 160 | 83.3
V250E3000 | 0.001, 0.003, 0.005 | 33, 28, 27 | 16
V250E500 | 0.000, 0.001, 0.002 | 96, 93, 91 | 57.8
V250E5000 | 0.002, 0.003, 0.008 | 20, 19, 18 | 11
V250E750 | 0.001, 0.002, 0.003 | 79, 68, 67 | 44
V300E1000 | 0.000, 0.002, 0.003 | 89, 79, 77 | 48.6
V300E2000 | 0.001, 0.001, 0.004 | 59, 54, 48 | 29.4
V300E300 | 0.001, 0.004, 0.005 | 193, 192, 192 | 100
V300E3000 | 0.001, 0.003, 0.007 | 42, 35, 33 | 22
V300E500 | 0.001, 0.002, 0.003 | 138, 125, 122 | 77.7
V300E5000 | 0.001, 0.005, 0.010 | 31, 27, 23 | 15.1
V300E750 | 0.001, 0.004, 0.005 | 114, 96, 93 | 59.6
V500E1000 | 0.002 ,0.004, 0.006 | 199, 187, 181 | 114.7
V500E10000 | 0.005, 0.008, 0.012 | 41, 40, 37 | 22.2
V500E2000 | 0.002, 0.008, 0.012 | 134, 116, 114 | 71.2
V500E500 | 0.003, 0.006, 0.013 | 329, 326, 326 | 167
V500E5000 | 0.004, 0.011, 0.021 | 67, 62, 60 | 36.9
V800E100 | 0.005, 0.014, 0.015 | 537, 528, 523 | 267
V800E1000 | 0.004, 0.011, 0.013 | 434, 421, 414 | 242.5
V800E10000 | 0.003, 0.009, 0.013 | 91, 83, 78 | 50.2
V800E2000 | 0.014, 0.015, 0.013 | 282, 266, 252 | 158.3
V800E5000 | 0.004, 0.012, 0.015 | 145, 138, 130 | 82.6
V1000E1000 | 0.010, 0.012, 0.014 | 677, 654, 654 | 333.7
V1000E10000 | 0.005, 0.012, 0.022 | 145, 129, 118 | 74
V1000E15000 | 0.006, 0.013, 0.020 | 100, 90, 87 | 55
V1000E20000 | 0.007, 0.018, 0.020 | 86, 75, 65 | 45
V1000E5000 | 0.006, 0.012, 0.014 | 226, 201, 197 | 121.1
Table 3. Experimental results for BHOSLIB benchmark for $m=0,2,5$. instance | time(s) $m=0,2,5$ | Sol Alg 1 | FastDS (Cai et al., 2020) | instance | time(s) $m=0,2,5$ | Sol Alg 1 | FastDS (Cai et al., 2020)
---|---|---|---|---|---|---|---
frb40-19-1 | 0.024, 0.032, 0.115 | 3, 3, 3 | 14 | frb50-23-4 | 0.023, 0.067, 0.089 | 7, 4, 4 | 18
frb40-19-2 | 0.023, 0.032, 0.061 | 6, 3, 3 | 14 | frb50-23-5 | 0.022, 0.075, 0.084 | 5, 3, 3 | 18
frb40-19-3 | 0.003, 0.034, 0.059 | 4, 4, 4 | 14 | frb53-24-1 | 0.032, 0.077, 0.094 | 3, 3, 3 | 19
frb40-19-4 | 0.023, 0.033, 0.084 | 3, 4, 4 | 14 | frb53-24-2 | 0.033, 0.096, 0.115 | 4, 3, 3 | 19
frb40-19-5 | 0.019, 0.035, 0.074 | 3, 3, 3 | 14 | frb53-24-3 | 0.032, 0.077, 0.094 | 3, 3, 3 | 19
frb45-21-1 | 0.022, 0.092, 0.098 | 5, 5, 4 | 16 | frb53-24-4 | 0.026, 0.086, 0.091 | 7, 6, 6 | 18
frb45-21-2 | 0.024, 0.045, 0.077 | 7, 6, 5 | 16 | frb53-24-5 | 0.029, 0.081, 0.098 | 5, 3, 3 | 19
frb45-21-3 | 0.022, 0.066, 0.078 | 3, 3, 3 | 16 | frb59-26-1 | 0.047, 0.109, 0.118 | 3, 3, 3 | 20
frb45-21-4 | 0.022, 0.047, 0.076 | 4, 4, 4 | 16 | frb59-26-2 | 0.029, 0.087, 0.107 | 3, 3, 3 | 21
frb45-21-5 | 0.032, 0.042, 0.075 | 3, 3, 3 | 16 | frb59-26-3 | 0.046, 0.114, 0.119 | 6, 3, 3 | 21
frb50-23-1 | 0.024, 0.064, 0.098 | 4, 4, 4 | 18 | frb59-26-4 | 0.031, 0.080, 0.155 | 3, 3, 3 | 21
frb50-23-2 | 0.023, 0.085, 0.087 | 4, 4, 4 | 18 | frb59-26-5 | 0.025, 0.099, 0.102 | 6, 3, 3 | 21
frb50-23-3 | 0.007, 0.063, 0.084 | 5, 3, 3 | 18 | frb100-40 | 0.083, 0.255, 0.550 | 3, 3, 3 | 36
Table 4. Experimental results for Network snap and DIMACS10 benchmark for $m=0,2,5$. instance | time(s) $m=0,2,5$ | Sol Alg 1 | FastDS (Cai et al., 2020)
---|---|---|---
Amazon0302(V262K E1.2M) | 4.322, 11.832, 21.681 | 82690, 71023, 68914 | 35593
Amazon0312(V400K E3.2M) | 7.833,19.076, 32.826 | 100960, 81107, 75368 | 45490
Amazon0505(V410K E3.3M) | 6.962,16.653, 29.229 | 91009, 78355, 72273 | 47310
Amazon0601(V403K E3.3M) | 6.844,15.708, 26.702 | 85559, 70372, 66267 | 42289
email-EuAll(V265K E420K) | 1.156, 2.208, 3.613 | 32007, 31935, 31925 | 18181
p2p-Gnutella24(V26K E65K) | 0.039, 0.117, 0.208 | 6056, 5724, 5569 | 5418
p2p-Gnutella25(V22K E54K) | 0.033, 0.084, 0.150 | 5066, 4771, 4637 | 4519
p2p-Gnutella30(V36K E88K) | 0.065, 0.201, 0.308 | 8067, 7559, 7379 | 7169
p2p-Gnutella31(V62K E147K) | 0.174, 0.496, 1.057 | 13917, 13123, 13086 | 12582
soc-sign-Slashdot081106(V77K E516K) | 0.198, 0.487, 0.845 | 16197, 15184, 15069 | 14312
soc-sign-Slashdot090216(V81K E545K) | 0.198, 0.487, 0.845 | 17291, 16290, 15871 | 15305
soc-sign-Slashdot090221(V82K E549K) | 0.381, 0.817, 1.383 | 16924, 16331, 16117 | -
soc-Epinions1(V75K E508K) | 2.050, 2.589, 3.298 | 17146, 16646, 16132 | 15734
web-BerkStan(V685K E7.6M) | 11.522, 28.080, 52.323 | 68449, 60265, 55912 | 28432
web-Stanford(V281K E2.3M) | 1.191, 2.824, 5.330 | 36928, 32956, 30845 | 13199
wiki-Talk(V2.3M E5M) | 5.447, 18.860, 35.098 | 40303, 39194, 39191 | 36960
web-NotreDame(V325K E1.5M) | 2.301, 6.293, 11.914 | 34788, 31929, 30883 | 23735
wiki-Vote(V7K E103K) | 2.155, 2.419, 2.663 | 1381, 1189, 1183 | 1116
cit-HepPh(V34K E421K) | 16.367, 18.854, 22.278 | 7476, 4866, 4305 | 3078
cit-HepTh(V27K E352K) | 11.972, 16.458, 21.249 | 6159, 4446, 4155 | 2936
rgg-n-2-17-s0 | 1.101, 2.649, 4.817 | 33789, 24020, 23595 | 43412
rgg-n-2-19-s0 | 14.948, 37.951, 69.568 | 127417, 88424, 86640 | 44423
rgg-n-2-20-s0 | 57.436,143.619, 265.936 | 248861, 170092, 166453 | 84708
rgg-n-2-21-s0 | 222.205, 554.531, 1021.933 | 487626, 328695, 320941 | 162266
rgg-n-2-22-s0 | 862.451, 2127.245, 3918.068 | 952637, 635144, 619729 | 312350
rgg-n-2-23-s0 | 3387.642, 8272.262, 15166.054 | 1866988, 1230026, 1199105 | 605278
citationCiteseer | 1.818, 5.231, 9.883 | 58985, 52797, 52512 | 43412
coAuthorsCiteseer | 1.322, 3.682, 7.144 | 40878, 38444, 38331 | 22011
co-papers-citeseer | 2.253 , 6.214 , 11.798 | 43879 , 37352 , 37043 | 26082
kron-g500-logn16 | 0.192 , 0.563 , 0.985 | 14300 , 14176 , 14173 | 14100
co-papers-dblp | 3.601 , 9.422 , 9.422 | 62670 , 52802 , 52196 | 43978
Table 5. Experimental results for Network repository benchmark for $m=0,2,5$. instance | time(s) $m=0,2,5$ | Sol Alg 1 | FastDS (Cai et al., 2020)
---|---|---|---
soc-youtube(V496k E2M) | 4.103, 12.808, 24.979 | 107611, 102464, 102366 | 89732
soc-flickr(V514K E3M) | 7.190, 22.538, 48.541 | 111049, 106455, 106326 | 98062
ca-coauthors-dblp(V540K E15M) | 3.679, 9.324, 17.806 | 62656, 52826, 52237 | 35597
ca-dblp-2012(V317K E1M) | 2.649, 7.648, 14.942 | 55071, 51946, 51841 | 46138
ca-hollywood-2009(V1.1 E56.3) | 11.049, 26.983, 46.099 | 75430, 62699, 61658 | 48740
inf-roadNet-CA(V2M E3M) | 405.566, 1219.695, 2436.119 | 900458, 856218, 841233 | 586513
inf-roadNet-PA(V1M E2M) | 125.252, 377.544, 750.686 | 528121, 501972, 498389 | 326934
rt-retweet-crawl(V1M E2M) | 12.787, 37.394, 72.781 | 84722, 82386, 81350 | 75740
sc-ldoor(V952K E21M) | 16.651, 46.390, 89.056 | 90654, 75095, 72627 | 62411
sc-msdoor(V416K E9M) | 2.770, 7.250, 13.904 | 28928, 25222, 23075 | 19678
sc-pwtk(V218K E6M) | 0.714, 2.236, 4.396 | 9088, 8552, 8482 | 4200
sc-shipsec1(V140K E2M) | 0.748, 1.871, 3.359 | 17577, 13273, 11863 | 7662
sc-shipsec5(V179K E2M) | 1.286, 3.421, 6.162 | 25243, 22899, 20236 | 10300
soc-FourSquare(V639K E3M) | 18.054, 28.809, 44,000 | 63643, 62245, 62050 | 60979
soc-buzznet(V101K E3M) | 0.216, 0.543, 0.932 | 201, 145, 138 | 127
soc-delicious(V536K E1M) | 3.708, 11.756, 22.703 | 58614, 57596, 55840 | 55722
soc-digg(V771K E6M) | 7.195, 19.044, 35.899 | 76454, 71018, 68846 | 66155
soc-flixster(V3M E8M) | 25.354, 73.153, 142.177 | 92197, 91516, 91010 | 91019
soc-lastfm(V1M E5M) | 8.326, 24.161, 45.156 | 68060, 67696, 67138 | 67226
soc-livejournal(V4M E28M) | 459.524, 1230.058, 2317.355 | 903243, 861908, 853903 | 793887
soc-orkut(V3M E106M) | 73.094, 174.005, 307.326 | 231177, 160436, 141907 | 110547
soc-orkut-dir(V3M E117M) | 68.837, 163.151, 292.163 | 230591, 213617, 201382 | 93630
soc-pokec(V2M E22M) | 46.195, 117.618, 215.056 | 301500, 241907, 239900 | 207308
soc-youtube-snap(V1M E3M) | 27.546, 80.038, 153.958 | 23587, 228008, 224933 | 213122
socfb-A-anon(V3M E24M) | 79.337, 185.572, 333.808 | 231903, 211315, 203021 | 201690
socfb-B-anon(V3M E21M) | 70.376, 165.034, 301.235 | 215288, 190114, 188315 | 187030
socfb-FSU53(V28K E1M) | 0.086, 0.213, 0.333 | 3683, 2545, 2309 | -
socfb-Indiana69(V30K E1M) | 0.099, 0.253, 0.422 | 3434, 2372, 2249 | -
socfb-MSU24(V32K E1M) | 0.099, 0.244, 0.404 | 4180, 3012, 2962 | -
socfb-Michigan23(V30K E1M) | 0.095, 0.237, 0.389 | 4109, 2953, 2712 | -
socfb-Penn94(V42K E1M) | 0.138, 0.344, 0.589 | 5588, 4137, 4044 | -
socfb-Texas80(V32K E1M) | 0.100, 0.251, 0.418 | 4357, 3104, 20725 | -
socfb-Texas84(V36K E2M) | 0.126, 0.321, 0.544 | 4211, 3148, 3084 | -
rec-epinions(V755K E13M) | 1.114, 4.026, 8.270 | 10116, 10076, 9766 | 9598
soc-dogster(V427K E9M) | 1.192, 2.894, 5.287 | 31000, 28300, 27261 | 26253
sc-rel9(V6M E24M) | 257.363, 731.034, 1375.043 | 230045, 201699, 197014 | 127548
rec-libimset-dir(V221K E17M) | 1.439, 4.262, 8.346 | 15229, 13910, 13225 | 12955
web-EPA | 0.01, 0.012, 0.016 | 361, 306, 303 | -
web-edu | 0.015, 0.045, 0.092 | 254, 254, 253 | -
web-polblogs | 0.003, 0.006, 0.012 | 128, 117, 117 | -
web-spam | 0.013, 0.018, 0.026 | 998, 918, 917 | -
web-frwikinews-user-edits | 0.032, 0.074, 0.092 | 696, 686, 686 | -
web-indochina-2004 | 0.016, 0.043, 0.088 | 1519, 1516, 1516 | -
web-webbase-2001 | 0.016, 0.043, 0.088 | 1519, 1516, 1516 | -
web-sk-2005 | 0.983, 2.662, 5.136 | 33767, 32345, 32305 | -
web-uk-2005 | 0.149, 0.496, 0.864 | 1719, 1719, 1719 | 1421
web-arabic-2005 | 0.639, 2.339, 3.781 | 21261, 20307, 20279 | -
web-Stanford | 0.392, 1.456, 3.046 | 21335, 19961, 19942 | -
web-NotreDame | 4.039, 8.443, 14.713 | 1197991, 1196608, 1196579 | -
web-BerkStan-dir | 10.358, 24.594, 42.32 | 6959022, 6955884, 6955817 | -
web-it-2004 | 4.193, 12.689, 25.002 | 34770, 34497, 34442 | 32997
web-italycnr-2000 | 1.832, 4.96, 9.72 | 26137, 24554, 24530 | -
web-wikipedia2009 | 103.305, 297.81, 590.188 | 421852, 400294, 399634 | 346581
web-google-dir | 12.913, 32.988, 59.198 | 4336976, 4325727, 4325505 | -
web-baidu-baike | 45.817, 127.943, 249.043 | 326856, 310844, 310441 | 277847

These experiments show that the fast running time and easy implementation of
our proposed algorithm enable us to compute reasonable solutions for really
large networks. This algorithm can be used in very large networks that
previous algorithms were not able to compute the solution because of time or
hardware limitations.

The quality of solutions in our algorithm is worse than (Cai et al., 2020) in
some benchmarks. however our results are at most 2 times of the results of
FastDS which is reasonable since as we said before our algorithm finds a total
dominating set which potentially can be 2 times larger than the dominating set
that the other algorithms find and also the algorithm is distributed and the
previous ones do not work in distributed setting. Obviously not all the
sequential algorithms can be made distributed with the same solution quality.
This happens in distributed algorithms for MDS problem as well. We wanted to
show that a simple and fast distributed algorithm can have reasonable
solutions. However because of the fast running time of our algorithm, it can
be use in sequential model in the case where we have time limit, since even
for small values of $m$, the algorithm gives reasonable results.

For the further experiments we solve the $k$-distance dominating set problem
on some of the large social networks instances. The instances are from the
network repository benchmark. We compare our results with the results of
(Nguyen et al., 2020). Their experiments are conducted on a computer with
Intel Core i7-8750h 2.2 GHz running Ubuntu OS. The programming language is
Python using igraph package to perform graph computations. In (Nguyen et al.,
2020) their algorithm known as HEU4 was compared with an algorithm called HEU3
from (Campan et al., 2016) and another greedy algorithm called HEU1 which was
used by their partner. In Table 6 the results are shown. As it can be seen our
algorithm has reasonable results in distributed model compared to their
results in sequential model. Note that again we cannot compare the running
times since the configuration of systems are different.

If we construct a graph $G^{\prime}$ from $G$ such that there is an edge
between two vertices $u$ and $v$ if their distance is at most $k$, then
solving the minimum $k$-distance dominating set for $G$ is equal to solving
MDS for $G^{\prime}$. This means that for larger values of $k$ the graph
$G^{\prime}$ will be denser than $G$. So we expect that our algorithm outputs
near optimal solutions for larger values of $k$ in dense graphs. In the
$k$-distance dominating set problem theoretically the algorithm needs $O(km)$
rounds because when a node wants to mark its neighbor with maximum $w_{i}$, it
needs $k$ rounds to receive $w_{i}$’s of neighbors within distance $k$ from
itself.

Table 6. Experimental results for Network repository benchmark for $m=0,2,5$ and $k=2$. instance | Alg 1 sol m=0,2,5 | Alg 1 time(s) m=0,2,5 | HEU1 sol | HEU1 time(s) | HEU4 sol | HEU4 time
---|---|---|---|---|---|---
soc-delicious | 32029, 18666, 17575 | 6.763, 18.937, 36.800 | 34516 | 3.57 | 8155 | 2064.00
soc-flixster | 46911, 20981, 17431 | 152.383, 413.453, 776.118 | 48789 | 85.93 | 9860 | 23694.58
soc-livejournal | 395992, 291846, 277713 | 269.600, 656.184, 1182.615 | 447552 | 1582.87 | 189121 | 16728.22

Note that we have implemented the sequential version of Algorithm 1 without
any change on the distributed version. In the distributed model all nodes are
executing at the same time, here at the same time in each round they choose
their neighbor with maximum $w_{i}$, in our sequential implementation the same
nodes are chosen but one by one as well. So the results of distributed
implementation and sequential implementation are the same.

We can modify this centralized version to improve the quality of the solution
and also reduce the running time. For example in the for loop that for each
vertex $v_{i}$ we choose a neighbor with maximum weight, we can have the
following modification. For each vertex $v_{i}$ if it is not dominated choose
a neighbor $u$ with maximum weight and dominate the vertices that are adjacent
to $u$. This modification can improve the quality of solution and the running
time since for the vertices that are dominated in the previous steps we do not
need to find the neighbor with maximum weight. Also for the running time we
have not tried to use fast algorithms for finding the neighbors within
distance $k$. But we have not done the above modifications because we want to
show the efficiency and easy implementation of Algorithm 1 in the distributed
model.

##  4\. Concluding remarks

In this paper we proposed a distributed algorithm for the MDS problem and also
$k$-distance dominating set problem. Theoretically, for MDS problem we
analyzed the approximation factor of Algorithm 1 for triangle free planar
graphs. As it can be seen in the proofs, the restriction for not having
triangles or $4$-cycles (in (Alipour and Jafari, 2020)) is used to get a graph
without multiple edges. Hence for a planar graph $G$ or even a general graph
$G$ with small crossing number, we can still use this algorithm to get a
possibly worse approximation factor. The crossing number of a graph $G$ is the
lowest number of edge crossings of a plane drawing of the graph $G$. For
instance, a graph is planar if and only if its crossing number is zero. In
practice as an example of such networks consider the network of streets in an
urban area where the streets are edges and the cross points of streets are
nodes. This graph is planar graph and it has a few number of triangles.

Also, as the experiments show by increasing $m$ in our algorithm the quality
of the solution increases. It is an interesting problem to theoretically see
how the approximation factors given in Theorem 2.1 change if one increases
$m$. The experiments suggest that for small values of $m$ this improvement is
significant and as $m$ increases to bigger numbers, the improvements are
marginal.

Also in a future work, one can modify the algorithm to solve the set-cover
problem. In the set-cover problem we are given a set
$A=\\{a_{1},a_{2},\dots,a_{n}\\}$ of $n$ elements and $m$ subsets,
$A_{1},A_{2},\dots,A_{m}$ of $A$. The goal is to choose the minimum number of
subsets that they cover all the elements of $A$. Again simply each element
$a_{i}$ chooses a subset $A_{j}$ with maximum size such that $a_{i}\in A_{j}$.
Then $x_{i}$’s are the number of times that $A_{i}$’s are chosen by the
elements. Then for $m$ rounds we repeat the algorithm.

Note that beside the fact that this algorithm is distributed we can easily
implement it in a dynamic model where the network is changing dynamically.
This is the case that happens in social networks constantly. When an edge is
added to the network, we can easily update the answer based on the added
vertex. Specially in the case of $m=0$, it is enough to change the answer of
those vertices that are connected to the added vertex and their neighbors. So
the update can be done very fast.

Here in the first step of algorithm, we consider the neighbor vertices with
maximum degrees. However based on the input graph one can modify the algorithm
and choose the initial vertices based on other properties.

## References

  * (1)
  * Abu-Khzam et al. (2017) Faisal N. Abu-Khzam, Shaowei Cai, Judith Egan, Peter Shaw, and Kai Wang. 2017\.  Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis. In _Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings_. 59–70.  https://doi.org/10.1007/978-3-319-55911-7_5
  * Alipour and Jafari (2020) Sharareh Alipour and Amir Jafari. 2020.  A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs. In _SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020_. 501–502.  https://doi.org/10.1145/3350755.3400217
  * Amiri et al. (2019) Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. 2019\.  Distributed Dominating Set Approximations beyond Planar Graphs.  _ACM Trans. Algorithms_ 15, 3 (2019), 39:1–39:18.  https://doi.org/10.1145/3326170
  * Bouamama and Blum (2016) Salim Bouamama and Christian Blum. 2016.  A hybrid algorithmic model for the minimum weight dominating set problem.  _Simul. Model. Pract. Theory_ 64 (2016), 57–68.  https://doi.org/10.1016/j.simpat.2015.11.001
  * Cai et al. (2020) Shaowei Cai, Wenying Hou, Yiyuan Wang, Chuan Luo, and Qingwei Lin. 2020.  Two-goal Local Search and Inference Rules for Minimum Dominating Set. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_. 1467–1473.  https://doi.org/10.24963/ijcai.2020/204
  * Cai et al. (2011) Shaowei Cai, Kaile Su, and Abdul Sattar. 2011.  Local search with edge weighting and configuration checking heuristics for minimum vertex cover.  _Artif. Intell._ 175, 9-10 (2011), 1672–1696.  https://doi.org/10.1016/j.artint.2011.03.003
  * Campan et al. (2016) Alina Campan, Traian Marius Truta, and Matthew Beckerich. 2016.  Approximation algorithms for d-hop dominating set problem. In _Proceedings of the International Conference on Data Mining (DMIN)_. The Steering Committee of The World Congress in Computer Science, Computer …, 86.
  * Chalupa (2018) David Chalupa. 2018\.  An order-based algorithm for minimum dominating set with application in graph mining.  _Inf. Sci._ 426 (2018), 101–116.  https://doi.org/10.1016/j.ins.2017.10.033
  * Chaurasia and Singh (2015) Sachchida Nand Chaurasia and Alok Singh. 2015.  A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set.  _Appl. Intell._ 43, 3 (2015), 512–529.  https://doi.org/10.1007/s10489-015-0654-1
  * Czygrinow et al. (2008) Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak. 2008\.  Fast Distributed Approximations in Planar Graphs. In _Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings_. 78–92.  https://doi.org/10.1007/978-3-540-87779-0_6
  * Fan et al. (2019) Yi Fan, Yongxuan Lai, Chengqian Li, Nan Li, Zongjie Ma, Jun Zhou, Longin Jan Latecki, and Kaile Su. 2019\.  Efficient Local Search for Minimum Dominating Sets in Large Graphs. In _Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Chiang Mai, Thailand, April 22-25, 2019, Proceedings, Part II_. 211–228.  https://doi.org/10.1007/978-3-030-18579-4_13
  * Garey and Johnson (1979) M. R. Garey and David S. Johnson. 1979.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  W. H. Freeman.
  * Gast et al. (2015) Mikael Gast, Mathias Hauptmann, and Marek Karpinski. 2015\.  Inapproximability of dominating set on power law graphs.  _Theor. Comput. Sci._ 562 (2015), 436–452.  https://doi.org/10.1016/j.tcs.2014.10.021
  * Gulati and Eirinaki (2019) Avni Gulati and Magdalini Eirinaki. 2019.  With a Little Help from My Friends (and Their Friends): Influence Neighborhoods for Social Recommendations. In _The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019_. 2778–2784.  https://doi.org/10.1145/3308558.3313745
  * Hedar and Ismail (2010) Abdel-Rahman Hedar and Rashad Ismail. 2010.  Hybrid Genetic Algorithm for Minimum Dominating Set Problem. In _Computational Science and Its Applications - ICCSA 2010, International Conference, Fukuoka, Japan, March 23-26, 2010, Proceedings, Part IV_. 457–467.  https://doi.org/10.1007/978-3-642-12189-0_40
  * Hilke et al. (2014) Miikka Hilke, Christoph Lenzen, and Jukka Suomela. 2014\.  Brief announcement: local approximability of minimum dominating set on planar graphs. In _ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014_. 344–346.  https://doi.org/10.1145/2611462.2611504
  * Karp (1972) Richard M. Karp. 1972\.  Reducibility Among Combinatorial Problems. In _Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA_ _(The IBM Research Symposia Series)_ , Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, New York, 85–103.  https://doi.org/10.1007/978-1-4684-2001-2_9
  * Karthik C. S. et al. (2018) Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. 2018\.  On the parameterized complexity of approximating dominating set. In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018_. 1283–1296.  https://doi.org/10.1145/3188745.3188896
  * Kuhn et al. (2016) Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2016\.  Local Computation: Lower and Upper Bounds.  _J. ACM_ 63, 2 (2016), 17:1–17:44.  https://doi.org/10.1145/2742012
  * Lenzen et al. (2013) Christoph Lenzen, Yvonne Anne Pignolet, and Roger Wattenhofer. 2013.  Distributed minimum dominating set approximations in restricted families of graphs.  _Distributed Computing_ 26, 2 (2013), 119–137.  https://doi.org/10.1007/s00446-013-0186-z
  * Lin et al. (2016) Geng Lin, Wenxing Zhu, and M. Montaz Ali. 2016.  An Effective Hybrid Memetic Algorithm for the Minimum Weight Dominating Set Problem.  _IEEE Trans. Evol. Comput._ 20, 6 (2016), 892–907.  https://doi.org/10.1109/TEVC.2016.2538819
  * Nguyen et al. (2020) Minh Hai Nguyen, Minh Hoàng Hà, Diep N Nguyen, et al. 2020\.  Solving the k-dominating set problem on very large-scale networks.  _Computational Social Networks_ 7, 1 (2020), 1–15.
  * Potluri and Singh (2011) Anupama Potluri and Alok Singh. 2011.  Two Hybrid Meta-heuristic Approaches for Minimum Dominating Set Problem. In _Swarm, Evolutionary, and Memetic Computing - Second International Conference, SEMCCO 2011, Visakhapatnam, Andhra Pradesh, India, December 19-21, 2011, Proceedings, Part II_. 97–104.  https://doi.org/10.1007/978-3-642-27242-4_12
  * Potluri and Singh (2013) Anupama Potluri and Alok Singh. 2013.  Hybrid metaheuristic algorithms for minimum weight dominating set.  _Appl. Soft Comput._ 13, 1 (2013), 76–88.  https://doi.org/10.1016/j.asoc.2012.07.009
  * Raz and Safra (1997) Ran Raz and Shmuel Safra. 1997.  A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In _Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997_. 475–484.  https://doi.org/10.1145/258533.258641
  * Sanchis (2002) Laura A. Sanchis. 2002\.  Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem.  _Algorithmica_ 33, 1 (2002), 3–18.  https://doi.org/10.1007/s00453-001-0101-z
  * Suomela (2013) Jukka Suomela. 2013\.  Survey of local algorithms.  _ACM Comput. Surv._ 45, 2 (2013), 24:1–24:40.  https://doi.org/10.1145/2431211.2431223
  * van Rooij and Bodlaender (2011) Johan M. M. van Rooij and Hans L. Bodlaender. 2011.  Exact algorithms for dominating set.  _Discret. Appl. Math._ 159, 17 (2011), 2147–2164.  https://doi.org/10.1016/j.dam.2011.07.001
  * Wang et al. (2018) Yiyuan Wang, Shaowei Cai, Jiejiang Chen, and Minghao Yin. 2018\.  A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs. In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden_. 1514–1522.  https://doi.org/10.24963/ijcai.2018/210
  * Wang et al. (2017) Yiyuan Wang, Shaowei Cai, and Minghao Yin. 2017.  Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function.  _J. Artif. Intell. Res._ 58 (2017), 267–295.  https://doi.org/10.1613/jair.5205
  * Wawrzyniak (2013) Wojciech Wawrzyniak. 2013\.  Brief announcement: a local approximation algorithm for MDS problem in anonymous planar networks. In _ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013_. 406–408.  https://doi.org/10.1145/2484239.2484281