=Paper=
{{Paper
|id=Vol-1949/ICTCSpaper05
|storemode=property
|title= Distributed Approximation Algorithms for k-dominating Set in Graphs of Bounded Genus and Linklessly Embeddable Graphs
|pdfUrl=https://ceur-ws.org/Vol-1949/ICTCSpaper05.pdf
|volume=Vol-1949
|authors=Andrzej Czygrinow,Michal Hanckowiak,Wojciech Wawrzyniak,Marcin Witkowski
|dblpUrl=https://dblp.org/rec/conf/ictcs/CzygrinowHWW17
}}
== Distributed Approximation Algorithms for k-dominating Set in Graphs of Bounded Genus and Linklessly Embeddable Graphs==
https://ceur-ws.org/Vol-1949/ICTCSpaper05.pdf
Distributed approximation algorithms for
k-dominating set in graphs of bounded genus
and linklessly embeddable graphs
Regular Submission
Andrzej Czygrinow1? , Michal Hanćkowiak2 , Wojciech Wawrzyniak2 , and
Marcin Witkowski2
1
Faculty of Mathematics and Computer Science
Adam Mickiewicz University, Poznań, Poland
mhanckow,wwawrzy, mw@amu.edu.pl
2
School of Mathematical and Statistical Sciences
Arizona State University, Tempe, AZ,85287-1804, USA.
aczygri@asu.edu
Abstract. A k-dominating set in a graph G = (V, E) is a set U ⊆ V
such that ever vertex of G is either in U or has at least k neighbors in
U . In this paper we give simple distributed approximation algorithms in
the local model for the minimum k-dominating set problem for k ≥ 2
in graphs with no K3,h -minor and graphs with no K4,4 -minor. In par-
ticular, this gives fast distributed approximations for graphs of bounded
genus and linklessly embeddable graphs. The algorithms give a constant
approximation ratio and run in a constant number of rounds. In addi-
tion, we will give a (1 + )-approximation for an arbitrary fixed > 0
which runs in O(log∗ n) rounds where n is the order of a graph.
1 Introduction
The minimum dominating set (MDS) problem is one of the most extensively
studied graph-theoretic questions. On one hand, it plays an important role in
graph theory, on the other, it admits many important applications. Its complex-
ity has been studied in many different computational models and for various
classes of graphs. In general, the problem is NP-hard [7], and it is even NP-hard
to find a (C log ∆(G))-approximation for some constant C [16]. In addition to
the above hardness results for the sequential model, similar restrictions apply to
the distributed complexity of the problem in general graphs. At the same time,
there has been much more success in devising efficient approximations for spe-
cific classes of graphs. In particular, the problem is much more tractable when
restricted to the family of planar graphs and an efficient deterministic approx-
imation algorithm for the minimum dominating set problem in planar graphs
was given in [13]. The algorithm from [13] gives a constant approximation of a
?
Research supported in part by Simons Foundation Grant # 521777.
minimum dominating set, runs in a constant number of rounds but uses long
messages (more than O(log n) bits).In [20], Wawrzyniak improved the analysis
from [13] and showed that the algorithm from [13] gives a 52-approximation. In
addition, in [19], Wawrzyniak proposed a local (constant-time) algorithm which
gives a 694-approximation of the minimum dominating set problem in planar
graphs which uses messages of length at most O(log n) and works in the port
numbering model. (In this model, which is similar to the Local model, no unique
identifiers are required but edges which are incident to a vertex are numbered,
see [18].)
In [2], the authors showed that essentially the same algorithm gives a constant
approximation of a minimum dominating set in graphs of bounded genus. In fact,
as proved in [2], no geometrical considerations are needed when analyzing the
procedure from [13] as the only requirement is that the underlying graph has no
K3,h as a minor.
Often a stronger notion of a domination is needed. For example, in some ap-
plications it can be desirable to require that every vertex in a graph is dominated
not by one vertex from a set but by k vertices for some k ∈ Z + . This can be
interpreted as a fault tolerance requirement; Servers are placed in a network so
that each vertex/client has direct access to k servers.
To define the problem formally we need some notation and terminology. Let
G = (V, E) be a graph with |V | = n. By NG (v) = {u ∈ V : uv ∈ E} we denote
the neighborhood of a vertex v ∈ V and by NG [v] = NG (v) ∪ {v} the closed
neighborhood of v. We use dG (v) (or d(v) if G is clear from the context) to
denote |NG (v)|. Set D ⊆ V is called a dominating set in G if every vertex in
V \ D is adjacent to a vertex in D. A minimum dominating set in a graph G is a
dominating set in G of the smallest size. For a positive integer k, a k-dominating
set in G is a subset D ⊆ V such that for every v ∈ V \ D, |N (v) ∩ D| ≥ k,
that is, for every vertex v ∈ V , v is in D or v has at least k neighbors in D.
In particular, a 1-dominating set is simply a dominating set. In addition, we
will say that a set W k-dominates set U in G, if every vertex from U \ W
has at least k neighbors in W . Note that other notions of k-domination have
been considered and many variants of the problem have been studied (see [8]).
The k-domination problem was proposed in [6] as a natural generalization of
the minimum dominating set problem. It has been studied extensively in graph
theory, where the main line of research is to establish upper bounds for γk (G), the
minimum size of a k-dominating set. It is known that the problem is NP-complete
in general graphs but can be solved in linear time in trees and series-parallel
graphs ([9]). Further generalizations of the k-dominating set were considered and
many slightly different variants have been proposed. The distributed complexity
of finding γk (G) (the k-MDS problem) were studied in [10] and [12]. In addition,
in [3] distributed approximation algorithms for the minimum k-dominating set
problem in planar graphs are proposed. In this paper, we will study distributed
complexity of the problem in two classes of graphs, graphs of bounded genus
and linklessly embeddable graphs. Both of these classes are proper minor-closed
families of graphs and in our algorithms and analysis we will not need any
geometric properties of the graphs as we will work in a slightly more general
setting by forbidding some graphs as minors. Let G be a graph, we say that H is
a minor of G (or that G has an H-minor) if H can be obtained from a subgraph
of G by sequence of edge deletions and contractions. We say that G contains a
subdivision of H (or that T H is a subgraph of G) if G contains a graph obtained
from H by replacing edges of H by independent paths of length at least one.
Let Sh denote the surface obtained from the sphere by adding h handles
(see [5] for a formal definition of this process). The genus of a graph G, g(G),
is the least integer h such that there is an embedding of a graph G into Sh . In
what follows we will not make any geometric arguments as our argument applies
to a bigger class of graphs than the class of graphs of genus at most g. Note
that if G is embeddable in a surface S, then the graphs obtained from G by
deleting an edge or contracting an edge are embeddable as well. Consequently
the class of graphs of genus at most g is a proper minor-closed family of graphs
and can be characterized by a finite set of forbidden minors. In addition, since
g(Km,n ) = d(m − 2)(n − 2)/4e (see [14]), we have that if g(G) ≤ g, then G has
no K3,4g+3 -minor. As in [2], we will work with the family of graphs Bh which
have no K3,h -minor.
In addition to the graphs with no K3,h -minor we will give a distributed
approximation algorithm for graphs with no K4,4 -minor. This, in particular,
yields an algorithms for linklessly embeddable graphs which are sometimes viewed
as 3-dimensional analogs of planar graphs. An embedding of a graph in R3 is
called linkless if every pair of (vertex) disjoint cycles are unlinked closed curves.
It is not difficult to see that K4,4 is not linklessly embeddable (the only fact that
will be needed).
We will consider the Local model ([15]), which is a synchronous message-
passing model in which vertices have unique identifiers from {1, . . . , n} where n
is the order of the graph. Computations proceed in rounds and in each round
a vertex can send messages to all its neighbors, can receive messages from its
neighbors and can perform some local computations. Neither the size of the
messages nor the amount of local computations is restricted in any way. An
algorithm is executed by the vertices of a network and its objective is to find
a solution to a problem (in our case the k-MDS problem) in this underlying
network.
Our contribution is twofold. First, we show that for graphs of bounded genus
there is an easy distributed algorithm which gives a constant approximation of
the minimum k-dominating set for k ≥ 2. This mirrors the corresponding result
for planar graphs. In addition, the same approach gives a constant approximation
for k ≥ 3 in linklessly embeddable graphs. The case k = 2 is different, and to
address it we use a modification of the algorithm from [13] and some ideas from
[2] and [1]. The above approximation algorithms run in a constant number of
rounds and give a constant approximation ratio. Further improvement of the
approximation ratio are left for future work. Second, we propose a distributed
approximation algorithm with approximation ratio of (1+) for every fixed > 0.
This algorithm runs in O(log∗ n) rounds where n is the order of the graph. This
algorithm combines the main procedure from [4] with some additional ideas.
The paper is structured as follows. In the next section, we state some pre-
liminary facts. In the following section we give the first (simple) approximation
algorithm for the minimum k-dominating set in graphs with no T Kh,k+1 . This
yields an algorithm for graphs of bounded genus for k ≥ 2 and for linklessly
embeddable graphs when k ≥ 3. In Section 4 we address the 2M DS problem
for graphs with no T K4,4 which gives, in particular, an algorithm for linklessly
embeddable graphs when k = 2. Finally, in Section 5, we discuss the (1 + )-
approximation.
2 Preliminaries
We will start our technical discussion with a few facts which will be used later.
We have the following bound for the number of edges in a graph with T Kh (see
[5]).
Lemma 1. If G is a graph such that |E(G)| ≥ 5h2 n, then G has T Kh .
We will also need a more general bound for E(G) in the case G has no Kp -minor.
The following was proved by Kostochka in [11].
Lemma 2 (Kostochka). There exists c ∈ R such that for every √ r ∈ Z + if G
is a graph on n vertices with no Kr -minor, then |E(G)| ≤ cr log rn.
One of the main tools used in the proofs will be lemmas from [1]. Let v be a
vertex in G and let S ⊆ V (G) \ {v}. Then a set of paths is called a v, S-fan if
every path starts at v, ends in a vertex from S which is the only vertex from S on
the path, and any two distinct paths have only v in common. For a dominating
set D in a graph G let Dk,l be the set of vertices v ∈ V (G) \ D such that there
is a v, D-fan subgraph in G consisting of k paths, each of length at most l. The
following two facts are proved in [1].
Lemma 3. For h, l ∈ Z + there is c such that the following holds. Let G be a
graph with no T Kh and let D be a dominating set in G. Then |Dh−1,l | ≤ c|D|.
In addition, we have the following fact.
Lemma 4. Let h ∈ Z + . For l, m ∈ Z + there is c = c(m, l) such that if G is
graph with no T Km,h and D is a dominating set in G then |Dm,l | ≤ c|D|.
3 First algorithm for graphs with bounded genus and
linklessly embeddable graphs
In our first algorithm (Procedure 1) we simply add to the solution all vertices
of sufficiently large degree and claim that this gives a constant approximation
of a k-dominating set. Specifically, we will show that in the case when k ≥ 2
and G has bounded genus or k ≥ 3 and G is linklessly embeddable, this gives
a constant approximation of a minimum k-dominating set. We will need the
following lemma in the analysis.
Lemma 5. Let k, h, q ∈ Z + be such that k ≤ q. If H = H[U, X] is a bipartite
graph such that |U | ≥ kq (h − 1) + 1, |X| ≤ q and for every vertex u ∈ U ,
dH (u) ≥ k, then H contains Kh,k .
Proof. The proof is similar to a proof of an upper bound for the extremal
number of a complete bipartite graph. Suppose H has no Kh,k . We will count
the number of k-stars (stars of degree k) with centers in U . On one hand, the
number of such k-stars is at least u∈U d(u)
P
k ≥ |U |. On the other hand, since
H has no Kh,k , the number of k-stars is at most |X|
k (h − 1). Consequently, if
|X|
|U | ≥ k (h − 1) + 1, then H contains Kh,k .
Let h, k ∈ Z + , set L := k+h
k (h − 1) + 2(k + h) + 1 and consider the following
procedure.
Procedure 1
1. For every v ∈ V (G), if d(v) ≥ L, then add v to D.
2. For every v ∈ V (G) \ D, if |N (v) ∩ D| < k, then add v to D.
3. Return D.
In fact we will proves something slightly more general.
Fact 1 For h, k ∈ Z + let L := k+h
k (h − 1) + 2(k + h) + 1. If G is a graph
with no T Kh+k+1 and no Kh,k+1 , then Procedure 1 applied to G with L returns
a k-dominating set of size O(γk (G)).
Proof. Let W := {v ∈ V (G) : d(v) ≥ L} and let D∗ be an optimal k-dominating
set. Then the number of vertices in G which have a neighbor in D∗ \ W is at
most (L − 1)|D∗ |. Suppose that v ∈ V (G) \ W has |N (v) ∩ W | < k and so
it is added to D in the second step of the algorithm. Then v is either in D∗
or has at least one neighbor in D∗ \ W and so the number of vertices added
in step 2 is at most L|D∗ |. Thus to show that |D| = O(γk (G)) it is enough
to show that |W | = O(|D∗ |). To that end, note that for every v ∈ W \ D∗ ,
N (v) \ D∗ is k-dominated by D∗ . If |N (v) ∩ D∗ | ≥ h + k, then v ∈ Dh+k,1 ∗
.
∗
Since G has no T Kh+k+1 , D is a k-dominating set and so a 1-dominating set,
by Lemma 3, the number of such vertices is O(|D∗ |). Thus we may assume
that |N (v) \ D∗ | > L − (h + k) and recall that N (v) \ D∗ is k-dominated by
D∗ . Consider a maximum matching M in G[N (v) \ D∗ , D∗ ] and note that if
∗
|M | ≥ h + k, then v ∈ Dh+k,2 . Thus we may assume that |M | < h + k. Since M
is a maximum matching in G[N (v) \ D∗ , D∗ ], if w ∈ N (v) \ (D∗ ∪ V (M ), then all
neighbors of w which are in D∗ are in V (M ) as otherwise we could increase M .
Consequently, |N (N (v)\(D∗ ∪V (M )))∩D∗ | ≤ |V (M )∩D∗ | < h+k. In addition,
|E(N (v)\(D∗ ∪V (M )), V (M )∩D∗ )| ≥ k|N (v)\(D∗ ∪V (M ))| because ∗
D is a k-
∗ k+h
dominating set,and , by definition of L, |N (v) \ (D ∪ V (M ))| ≥ k (h − 1) + 1.
Thus, by Lemma 5, G[N (v) \ (D∗ ∪ V (M )), V (M ) ∩ D∗ ] contains Kh,k , which in
connection with v gives Kh,k+1 contradicting the fact that G has no T Kh,k+1 .
∗
The contradiction shows that |M | ≥ h + k and so v ∈ Dh+k,2 . By Lemma 3,
∗
|Dh+k,2 | = O(γk (G)).
We immediately get constant approximations for γk (G) in linklessly embed-
dable graphs for k ≥ 3.
Corollary 2 Let G be a linklessy embeddable graph and let k ≥ 3. Then Proce-
dure 1 applied to G returns a k-dominating set of size O(γk (G)) when applied
with h = 4.
Proof. Since G is linklessly embeddable, G has no K4,4 -minor and therefore no
K4,4 and no T K8 . We can apply Procedure 1 with h = 4.
If G is a graph with g(G) ≤ g, then G has no K4g+3,3 -minor. Consequently
Procedure 1 can be applied to G for every k ≥ 2 gives a constant approximation.
Corollary 3 Let g ∈ Z + and k ≥ 2. For every graph G with g(G) ≤ g, Proce-
dure 1 returns a k-dominating set of size O(γk (G)) when applied with h = 4g +3.
Proof. Since G has genus bounded by g, G ∈ B4g+3 , and so G has no T K4g+3,3 .
4 Graphs with no T K4,4 for k = 2
In the case G has no K4,4 -minor and k = 2 it is no longer possible to claim that
Procedure 1 gives a constant approximation of γk (G) and a slightly more
involved algorithm is needed. We will show that a modification of the algorithm
for the minimum dominating set in planar graphs from [13] gives a constant
approximation in this case. Recall that we say that a vertex v is 2-dominated by
a set S if either v ∈ S or v has at least two neighbors in S.
We will start with the following observation.
Lemma 6. Let K ∈ Z + . If U is a subset of V (G) such that |U | ≥ 4K 2 and
there is a set S ⊆ V (G) \ U of size |S| ≤ K which 2-dominates U , then there
exist s1 , s2 ∈ S such that s1 6= s2 and |N (s1 ) ∩ N (s2 ) ∩ U | ≥ 4.
Proof. Clearly there exists s1 ∈ S such that |N (s1 ) ∩ U | ≥ 4K 2 /K = 4K and
there exists s2 ∈ S \ {s1 } such that |N (s2 ) ∩ (N (s1 ) ∩ U )| ≥ 4K/K ≥ 4.
In what follows, let K := 642, C := 4K 2 + K and L := 4C + 3. We will
assume that G has no T K4,4 .
Procedure 2
1. For every v ∈ V (G): If there is no set S ⊆ V \ {v} such that |S| ≤ K and S
2-dominates N (v), then add v to D1 . In addition if d(v) < 2, then add v to
D1 .
2. Let Z be the set of vertices which are 2-dominated by D1 and let d0 (v) :=
|N (v) \ Z| for v ∈ V .
3. For every u ∈ V \ Z:
– If |N (u)∩D1 | = 1, then choose v ∈ N (u)\D1 such that d0 (v) is maximum
and add it to D2 .
– If |N (u) ∩ D1 | = 0, then choose two distinct v, v 0 ∈ N (u) with the largest
degrees d0 and add them to D2 .
4. Return D1 ∪ D2 .
Note that Procedure 2 works in the Local model as in the second step a vertex
v can obtain locally information about the ball of radius two centered at v to
determine if it should be added to D1 .
We first note that D1 ∪ D2 is a 2-dominating set.
Fact 4 The set D1 ∪ D2 is a 2-dominating set in G.
Proof. Suppose u ∈ / D1 and |N (u) ∩ D1 | = i for i = 0, 1. Then d(u) ≥ 2, and
so u has at least 2 − i neighbors in V \ D1 . In the second step of the procedure
2 − i of them will be added to D2 .
Let D∗ be an optimal 2-dominating set in G. We will now show that |D1 ∪
D2 | ≤ C|D∗ | for some constant C.
Fact 5 |D1 | = O(|D∗ |).
Proof. First note that if d(v) < 2, then v ∈ D∗ . In addition, for v ∈ D1 \ D∗ ,
we certainly have |N (v)| > K because N (v) is an option for S. Let V1 :=
{v ∈ D1 \ D∗ : |N (v) ∩ D∗ | ≥ K/2}. We have K|V1 |/2 ≤ |EG (V1 , D∗ )| <
5 · 64(|V1 | + |D∗ |) by Lemma 1, and so |V1 | < 320|D∗ |. Let V2 := {v ∈ D1 \ D∗ :
|N (v) ∩ D∗ | < K/2}. Take v ∈ V2 and let W ⊆ D∗ be a minimum set which 2-
dominates N (v)\D∗ . We have |W | ≥ K/2 because W ∪(N (v)∩D∗ ) 2-dominates
N (v). In addition, |N (v) \ D∗ | = |N (v)| − |N (v) ∩ D∗ | > K/2. Therefore, by
minimality of W , there is a matching of size at least |W |/2 ≥ K/4 ≥ 4 between
W and N (v) \ D∗ , and consequently there is a v, W2 -fan of size four. Therefore,
∗
v ∈ D4,2 and, by Lemma 4, |V2 | = O(|D∗ |).
To show that |D1 ∪ D2 | = O(|D∗ |) we will now prove that |D2 | = O(|D∗ |).
Fact 6 |D2 | = O(|D∗ |).
Proof. If D∗ \ D1 = ∅, then every vertex in V \ D1 has two neighbors in D1 and
D2 = ∅. For a vertex u ∈ V \ (Z ∪ D∗ ) which has one neighbor in D1 , there is
at least one v ∈ D∗ \ D1 such that u ∈ N (v). We fix one such v and say that u
belongs to v. If u has no neighbors in D1 , then there exist at least two vertices
v, v 0 ∈ D∗ \ D1 such that u ∈ N (v) ∩ N (v 0 ). We fix such a pair (v, v 0 ) and say
that u belongs to v if d0 (v) < d0 (v 0 ) (if the degrees are equal then we select one
of v, v 0 arbitrarily.)
Note that every vertex u ∈ V \ Z is either in D∗ \ D1 or belongs to exactly
one vertex from D∗ \ D1 .
In order to show that |D2 | = O(|D∗ |) we will argue that for every vertex
v ∈ D∗ \ D1 there can be at most a constant number of vertices added to D2
by v and by vertices which belong to v. Let v ∈ D∗ \ D1 . Note that v can
select at most two vertices to be added to D2 . In addition, there exists a set
S ⊆ V \ {v} such that |S| ≤ K and S 2-dominates N (v). Fix such a set S
and call it Sv . Let Ñ (v) be the set of u ∈ N (v) such that u belongs v. First
suppose |Ñ (v)| ≤ L. Since each u ∈ Ñ (v) selects at most two vertices in step 3,
the number of vertices added to D2 by vertices from Ñ (v) is at most 2L. Now
assume |Ñ (v)| > L. Let w ∈ V \ (D1 ∪ D∗ ∪ Sv ) and suppose w has a neighbor in
Ñ (v). If |N (w) ∩ Ñ (v)| > C, then Sv 2-dominates (N (w) ∩ Ñ (v)) \ Sv which has
size at least 4K 2 , and so by Lemma 6, G contains K4,4 which is not possible. Thus
0 < |N (w) ∩ Ñ (v)| ≤ C for every vertex v. For a vertex x, if u ∈ N (w) ∩ Ñ (x),
u belongs to x and d0 (x) > L. Thus if u selects w in step 3, then d0 (w) > L.
All neighbors of w in G[V \ Z] are either in D∗ \ D1 or in one of the sets Ñ (x).
If w has four neighbors in D∗ , then w ∈ D4,1 ∗
. Otherwise, w has at least one
neighbor in Ñ (x) for at least (L − 3)/C ≥ 4 vertices x ∈ D∗ \ D1 . Consequently,
by Lemma 4, the number of such vertices is O(|D∗ |). Finally, since |Sv | ≤ K,
there are at most K vertices in Sv which can be added to D2 by vertices in Ñ (v)
in step 3.
Thus we have the following theorem.
Theorem 7. There exists C ∈ Z + such that the following holds. Let G be a
graph with no T K4,4 . Then Procedure 2 finds a 2-dominating set D such that
|D| ≤ Cγ2 (G).
From Theorem 7, we get a constant approximation for the 2-minimum dominat-
ing set problem in linklessly embeddable graphs.
Corollary 8 Let G be a linklessy embeddable graph. Then Procedure 2 applied
to G returns a 2-dominating set of size O(γ2 (G)).
5 (1 + )-approximation
In this section we will show that a modification of the approach from [4] gives a
(1 + )-approximation of the k-dominating set for k ≥ 2 in the class of graphs of
bounded genus as well as in the class of linklessly embeddable graphs. In fact,
our main algorithm is much more general and applies to the class of graphs with
no Kp -minor for some fixed positive integer p. Let G be a graph on n vertices
with no Kp as a minor and suppose ω : E(G) → Z + is a weight function. For
a partition (V1 , . . . , Vl ) of V (G), we will denote by G̃ = G̃(V1 , . . . , Vl ) the graph
obtained from G by contracting
P each of the sets Vi to a vertex vi and setting
the weight ω(vi vj ) = e∈E(Vi ,Vj ) ω(e) when E(Vi , Vj ), the set of edges with one
endpoint in Vi and another in Vj , is non-empty. A straightforward generalization
of the main clustering procedure from [4] gives the following theorem.
Theorem 9. Let p ∈ Z + and let > 0. There exists C such that the following
holds. Suppose G is a graph on n vertices with no Kp -minor and let ω : E(G) →
Z + . There is a distributed algorithm which finds a partition (V1 , . . . , Vl ) such
that G[Vi ] has diameter O(C) and
X X
ω(e) ≤ ω(e).
e∈G̃ e∈G
The algorithm runs in C log∗ n rounds.
By combining Theorem 9 with some additional analysis we obtain the following
fact.
Theorem 10. Let p, k ∈ Z + and let δ > 0. Let G be a graph on n vertices with
no Kp -minor and suppose Q is a k-dominating set for G. There is a distributed
algorithm which finds a k-dominating set D in G such that
|D| ≤ γk (G) + δ|Q|.
The algorithm runs in C log∗ n rounds where C depends on p, k and δ only.
Note that the case k = 1 is proved in [4] but the algorithm from [4] doesn’t
address the situation k > 1 and a slightly different approach is needed. Before
proving Theorem 10 let us note that in view of the results from the previous
section we have the following corollaries.
Corollary 11 Let g, k ∈ Z + such that k ≥ 2 and let > 0. Let G be a graph
on n vertices with genus g. There is a distributed algorithm which finds a k-
dominating set D in G such that |D| ≤ (1 + )γk (G). The algorithm runs in
C log∗ n rounds where C depends only on g, k and .
Proof. In view of Corollary 3, there is a distributed algorithm which in a con-
stant number of rounds finds a k-dominating set Q in G such that |Q| ≤ LγK (G)
for some constant L. Let δ := /L. The by Theorem 10 finds a dominating set
D such that |D| ≤ (1 + )γk (G).
In addition, using the algorithms for linklessly embeddable graphs from pre-
vious sections we obtain the following fact.
Corollary 12 Let k ≥ 2 and let > 0. Let G be a linklessly embeddable graph
on n vertices. There is a distributed algorithm which finds a k-dominating set D
in G such that |D| ≤ (1 + )γk (G). The algorithm runs in C log∗ n rounds where
C depends only on k and .
Proof of Theorem 10. Let Q be a k-dominating set in G. Let G0 be the
following oriented graph obtained form the bipartite graph G[Q, V (G) \ Q]. We
put the arc from v to w for every edge vw with v ∈ V (G) \ Q and w ∈ Q. Since
Q is k-dominating, every vertex v ∈ V (G) \ Q has at least k out-neighbors in G0 .
By choosing one such out-neighbor arbitrarily, we obtain a set of stars S1 , . . . , Sl
with centers in vertices from Q. Let Uj := V (Sj ) and let cUj denote the center
of Sj , that is {cUj } = Uj ∩ Q. We will refer to sets Uj as small clusters. Let
H0 be the digraph obtained from G0 by contracting each Sj to a vertex. (Note
that it is possible
√ to have both arcs Uj Ui and Ui Uj in H0 .) Let D := ∅ and let
K := 2c · p log pk/δ where c is the constant in Lemma 2.
We will modify the original small clusters and construct a sequence of di-
graphs H1 , . . . , Hk−1 by increasing D in each step so that |D| is small with
respect to |Q| and clusters in Hk−1 obtained by deleting vertices which are k-
dominated by D have out-neighbors in at most K other vertices from Q. Some
of the centers of small clusters will be added to D, some vertices will be reas-
signed from one cluster to another, and, in addition, some vertices will become
k-dominated by D and will become inactive. Although we no longer need to k-
dominate inactive vertices (as they are k-dominated by D), they can still play an
important role because they themselves can be inside an optimal k-dominating
set. Although the sets Uj will change as we modify them, we will use Uj to re-
fer to the cluster determined by cUj during the execution of the algorithm. For
cluster U we use U 00 to denote the set of inactive vertices in U \ {cU } and we set
U 0 := U \ U 00 . Initially, U 00 := ∅ for every cluster U and we set B0 := V (G) \ Q.
We will now describe our procedure which modifies the small clusters. We will
use d+F (X) to denote the number of out-neighbors of a cluster X in F . Recall
that clusters are associated with their centers and so cluster X at step i can be
different than X at step j for i 6= j.
For the general step, assume i ≥ 1 and let Xi−1 := {U |d+ 0
Hi−1 (U ) > K}. If
U ∈ Xi−1 , then add cU to D. Consider v ∈ Bi−1 ∩ U 0 . If v becomes k-dominated
by D, then move v to U 00 and otherwise, add v to Bi . Every vertex v ∈ Bi has
at most k − 1 neighbors in D and so there exists a small cluster W such that
cW ∈ / D and vcW ∈ G0 . Let v join one such cluster W .
Let Hi be obtained by contracting each small cluster U to a vertex and by
adding the arc U W if the set of arcs from U 0 to W 0 in G0 is non-empty.
We will prove the following lemma.
Lemma 7. The following holds:
Pk
(a) i=1 |Xi−1 | < δ|Q|/2.
(b) For every v ∈ Bk , |NG (v) ∩ D| ≥ k.
(c) For every small cluster U there exists a set of small clusters Q0 ⊆ Q such
that |Q0 | ≤ K and every vertex v ∈ U \ (Bk ∪ {cU }) has NG (v) ∩ Q ⊆ Q0 ∪ D.
To prove the lemma we will show a sequence of claims. Part (a) follows from the
following observation.
Claim. |Xi−1 | < δ|Q|/(2k).
√
Proof. From Lemma 2, U ∈Hi−1 d+
P
Hi−1 (U ) = |E(Hi−1 )| ≤ cp log p|Q|. Thus
√
|Xi−1 | < cp log p|Q|/K = δ|Q|/(2k).
We will now verify part (b).
Claim. If v ∈ Bi , then |NG (v) ∩ D| ≥ i.
Proof. This is certainly true when i = 0. Suppose i ≥ 1. If v ∈ Bi , then v ∈ Bi−1
and in the ith step of the procedure v ∈ U 0 for some U ∈ Xi−1 . Since cU is added
to D, |NG (v) ∩ D| increases by at least one.
Part (c) is slightly more involved and we split the argument into two claims.
First note the following.
Claim. If U ∈ Xi , then U ∈
/ Xi+1 .
Proof. We proceed by induction on i. If U ∈ X0 , then after adding cu to D and
partitioning U into U 0 and U 00 , every vertex from U 0 is reassigned and so in the
next step U 0 is empty. Suppose U ∈ Xi . Then, by induction, U ∈ / Xi−1 . Thus
some vertices from Bi−1 joined U , as this is the only way for the out-degree of
a cluster to increases. Each such vertex is either inactive or is in Bi after cU is
added to D in the ith step, and every vertex from Bi ∩ U joins a cluster different
than U with center which is not in D. Consequently, none of these added vertices
is in U 0 in the iteration i + 1, and we have d+ 0 + 0
Hi+1 (U ) ≤ dHi−1 (U ).
Claim. Let i ≥ 1. For every U there exists a set Q0 ⊆ Q such that |Q0 | ≤ K and
for every vertex v ∈ U \ (Bi ∪ {cU }), NG (v) ∩ Q ⊆ Q0 ∪ D.
Proof. If U ∈ / Xi then d+ 0 0
Hi (U ) ≤ K and so NG (U \ (Bi ∪ {cU })) ∩ Q ⊆
0 0
Q for some set Q of size at most K. Suppose U ∈ Xi . Then U ∈ / Xi−1 by
Claim 5. Therefore some vertices from Bi−1 joined U and each of them is either
inactive (and dominated by D) or is in Bi . Consider U 0 in the ith iteration of
the procedure. The set U 0 is a subset of the union of X and Y , where X is the
set U 0 \ Bi−1 from the iteration i − 1 and Y is the set of vertices added to the
small cluster U in the ith iteration. The number of distinct out-neighbors of X
in Q is therefore at most K, and the vertices from Y are either dominated by D
or are in Bi .
This proves part (c) of the lemma.
We will now continue with the proof of Theorem 10.
Let U1 , . . . , Ul denote the clusters in Hk and recall that l = |Q|. Let G∗
be obtained from G by contracting each Ui to a vertex√ ui . In addition, set
ω(ui uj ) = 1 for every edge ui uj ∈ G∗ . Let := δ/(6c · p log pK) and use the
clustering procedure from Theorem 9 to find a partition P of {u1 , . . . , ul } into
V1 , . . . , Vs . Then
p
ω(G̃) ≤ |E(G)| ≤ · cp log pl < δl/(6K).
Let ∂P be the set of u ∈ {u1 , . . . , ul } such that for some i 6= j, u ∈ Vi and
NG∗ (u) ∩ Vj 6= ∅. We have |∂P | ≤ 2ω(G̃) ≤ δl/(3K).
Let u ∈ ∂P and consider the small cluster U which was contracted to u. Add
cU to D and note that by Lemma 7 (b) every vertex v ∈ Bk ∩ U has k-neighbors
in D. In addition, by Lemma 7 (c), there is a set Q0 of at most K vertices in Q
such that every vertex v ∈ U \ (Bk ∪ {cU }) has NG (v) ∩ Q ⊆ Q0 ∪ D. Since every
vertex v ∈ V (G) \ Q has at least k neighbors in Q, by adding Q0 ∪ {cU } to D
we k-dominate all vertices from U . Add Q0 ∪ {cU } to D for every U ∈ ∂P . By
Lemma 7 (a), we have
|D| ≤ δ|Q|/2 + δl(K + 1)/(3K) < δ|Q|.
S
Let Wi := U ∈Vi \∂P U . Since the diameter of G[Vi ] is O(1), it is possible to find
in O(1) rounds an optimal set Di ⊆ Vi such that Di ∪ D k-dominates Wi . Let
Sl
D0 := i=1 Di ∪ D and let D∗ denote an optimal k-dominating set in G. Then
X X
|D0 | ≤ |Di | + |D| ≤ |D∗ ∩ Vi | + |D| ≤ |D∗ | + |D| < γk (G) + δ|Q|
where the second inequality follows from the fact that every vertex
S in Wi can
be k-dominated only by vertices in Vi ∪ D and every vertex in U ∈∂P U is k-
dominated by D.
References
1. N. Alon, S. Gutner: Kernels for the Dominating Set Problem on Graphs with an
Excluded Minor, Electronic Cooloquium on Computational Complexity, Report No.
66, (2008).
2. S. A. Amiri, S. Schmid, S. Siebertz: A Local Constant Factor MDS Approximation
for Bounded Genus Graphs, PODC 2016, Proceedings of the 2016 ACM Symp. on
Principles of Distributed Computing, (2016), 227–233.
3. A. Czygrinow, M. Hanćkowiak, E. Szymańska, W. Wawrzyniak, and M. Witkowski:
Improved distributed local approximation algorithm for minimum 2-dominating set
in planar graphs, Theoretical Computer Science, Vol 662, (2017), pages 1–8 .
4. A. Czygrinow, M. Hanćkowiak, and W. Wawrzyniak: Fast distributed approxima-
tions in planar graphs, International Symposium on Distributed Computing, DISC,
Arcachon, France, September 2008, LNCS 5218, pages 78–92.
5. R. Diestel: Graph Theory 4th Ed., Springer, 2010.
6. J.F. Fink, M.S. Jacobson: n-domination in graphs, Graph Theory with Applications
to Algorithms and Computer Science,1985, pages 282–300.
7. M. R. Garey and D. S. Johnson: Computers and Intractability, Freeman, 1979.
Lower bounds for local approximation, J. ACM 60(5): 39, 2013, pages 1–23.
8. T. Haynes, S. Hedetniemi, P. Slater: Domination in Graphs: Advanced Topics,
Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker,
1998.
9. M.S. Jacobson, K. Peters: Complexity questions for n-domination and related pa-
rameters, Congr. Numer. (68), 1989, pages 7–22.
10. L. Jia, R. Rajaraman, R. Suel: An efficient distributed algorithm for constructing
small dominating sets, Distributed Computing, 15(4), 2002, pages 193–2005.
11. A. V. Kostochka: The minimum Hadwiger number for graphs with a given mean
degree of vertices, Metody Diskret. Analiz. (in Russian), 38, (1982), pages 37-58.
12. F. Kuhn, T. Moscibroda, R. Wattenhofer: Fault-Tolerant Clustering in Ad Hoc
and Sensor Networks, ICDCS 2006, pages 68–78.
13. C. Lenzen, Y. A. Oswald, R. Wattenhofer: Distributed minimum dominating set
approximations in restricted families of graphs, Distrib. Comput., 26 (2), 2013,
pages 119–137.
14. B. Mohar, C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press,
(2001).
15. D. Peleg: Distributed Computing: A Locality-Sensitive Approach, Society for Indus-
trial and Applied Mathematics, Philadelphia, PA, USA, 2000.
16. R. Raz, S. Safra: A Sub-Constant Error-Probability
17. N. Robertson, P. Seymour, R. Thomas: Sachs’ linkless embedding conjecture, Jour-
nal of Combinatorial Theory, Series B, 64, (1995), 185–227.
18. J. Suomela: Survey of local algorithms, ACM Comput. Surv. 45(2): 24, 2013, pages
1–40.
19. W. Wawrzyniak: A local approximation algorithm for minimum dominating set
problem in anonymous planar networks. Distributed Computing 28(5), 2015, pages
321–331.
20. W. Wawrzyniak: A strengthened analysis of a local algorithm for the minimum
dominating set problem in planar graphs, Inf. Process. Lett. 114(3), 2014, pages
94–98.