Distributed Domination on Graph Classes
of Bounded Expansion
Saeed Akhoondian Amiri∗1 , Patrice Ossona de Mendez
Roman Rabinovich∗1 , and Sebastian Siebertz ‡3

†2

,

arXiv:1702.02848v1 [cs.DC] 9 Feb 2017

saeed.amiri@tu-berlin.de, pom@ehess.fr, roman.rabinovich@tu-berlin.de,
siebertz@mimuw.edu.pl
1 Technische

Universität Berlin, Germany
(CNRS UMR 8557), EHESS, Paris, France
3 Institute of Informatics, University of Warsaw, Poland
2 CAMS

We provide a new constant factor approximation algorithm for the (connected)
distance-r dominating set problem on graph classes of bounded expansion. Classes
of bounded expansion include many familiar classes of sparse graphs such as planar
graphs and graphs with excluded (topological) minors, and notably, these classes
form the most general subgraph closed classes of graphs for which a sequential
constant factor approximation algorithm for the distance-r dominating set problem
is currently known. Our algorithm can be implemented in the CON GEST BC model
of distributed computing and uses O(r2 log n) communication rounds.
Our techniques, which may be of independent interest, are based on a distributed
computation of sparse neighborhood covers of small radius on bounded expansion
classes. We show how to compute an r-neighborhood cover of radius 2r and
overlap f (r) on every class of bounded expansion in O(r2 log n) communication
rounds.
Finally, we show how to use the greater power of the LOCAL model to turn any
distance-r dominating set into a constantly larger connected distance-r dominating
set in 3r + 1 rounds on any class of bounded expansion. Combining this algorithm,
e.g., with the constant factor approximation algorithm for dominating sets on
planar graphs of Lenzen et al. gives a constant factor approximation algorithm
for connected dominating sets on planar graphs in a constant number of rounds
in the LOCAL model, where the approximation ratio is only 6 times larger than
that of Lenzen et al.’s algorithm.
∗

S.A. Amiri, R. Rabinovich and, partially, S. Siebertz’s research was supported by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC
consolidator grant DISTRUCT, agreement No 648527).
†
P. Ossona de Mendez’s research was supported by grant ERCCZ LL-1201 and by the European Associated
Laboratory “Structures in Combinatorics” (LEA STRUCO), and partially supported by ANR project Stint
under reference ANR-13-BS02-0007
‡
Contact author. Address: Institute of Informatics, Faculty of Mathematics, Informatics, and Mechanics of
the University of Warsaw ul. Banacha 2, 02-097 Warsaw, Poland. Telephone number: +48 22 5544458.
The work of S. Siebertz is partially supported by the National Science Centre of Poland via POLONEZ
grant agreement UMO-2015/19/P/ST6/03998, which has received funding from the European Union’s
Horizon 2020 research and innovation programme (Marie Skłodowska-Curie grant agreement No. 665778).

1

1 Introduction and contributions
The Dominating Set problem is one of the most fundamental problems in algorithmic graph
theory and complexity theory. Given a graph G, the problem is to find a minimum size subset
D ⊆ V (G) such that every vertex w ∈ V (G) has distance at most one to a vertex in D.
A number of generalisations and variations of the Dominating Set problem have been
studied. In the Distance-r Dominating Set problem, we are given a graph G and an
integer parameter r and we are asked to find a minimum size set D such that every vertex
in G has distance at most r to a vertex in D. By setting r = 1 we obtain the original
Dominating Set problem. The problem is also known as the (k, r)-center problem and has
been extensively studied in the literature, especially in the distributed community, where
it finds applications in distributed databases, routing and distributed data structures, see,
e.g., [12, 14, 26, 31, 39, 45, 46, 55, 54, 56].
Another problem is the Connected Dominating Set problem, and its distance-r variant,
where we ask for a (distance-r) dominating set which is connected. Also this problem has
received considerable interest in the literature, see, e.g., [18, 19, 67, 70]. We also refer to the
recent survey on distributed computing and on more applications [63].
Finding a minimum size dominating set in a graph G is NP-complete in general [35], and
even so in very restricted settings, e.g., on planar graphs of maximum degree 3 (cf. [GT2]
in [25]). Therefore it is believed that there is no efficient algorithm that finds a smallest
dominating set for a given graph in general, and consequently, much effort has been made to
find good approximations.
Of course, the Distance-r Dominating Set problem trivially reduces to the Dominating
Set problem by connecting in the input graph all vertices that are at distance at most r from
each other. However, this may lead to the introduction of many edges even if the input graph
is very sparse, which may be problematic, e.g., in large databases where linear time algorithms
are crucial. Furthermore, much structural information available on the input graph, e.g.,
planarity, may be lost when introducing these edges. Therefore, a direct solution to the more
general problem is desirable.
There is a simple greedy algorithm to approximate dominating sets: at each step add a
vertex to the dominating set which dominates the largest number of non-dominated vertices.
This algorithm on an n-vertex graph achieves an approximation ratio of ln n − ln ln n +
Θ(1) [16, 33, 43, 60, 61]. Note that these results are for the Set Cover problem, which
however reduces to the Dominating Set problem by an approximation preserving reduction and, in fact, the two problems achieve exactly the same approximation ratio [34]. In
general, no better approximation ratio can be achieved under standard complexity theoretic
assumptions [4, 6, 13, 21, 24, 44, 58].
The Dominating Set problem is more manageable when restricted to some special classes
of sparse graphs. For example, there exists a PTAS for Dominating Set in planar graphs [10],
minor closed classes of graphs with local bounded tree-width [23] and graphs with excluded
minors [27]. Most recently, it was shown that Distance-r Dominating Set admits a PTAS
on every graph class with polynomial expansion [30].
All these classes are examples of classes with bounded expansion, a very general model of
uniform sparseness in graphs introduced by Nešetřil and Ossona de Mendez [48, 49, 47] (see
also [52] for other examples of classes with bounded expansion). A motivating observation to
the theory of classes with bounded expansion is that the classical notion of sparseness (the
ratio of edges to vertices) is not necessarily sufficient for algorithmic tractability. Similarly, the
notion of degeneracy and a closely related notion of arboricity, which are stronger notions of

2

uniform sparseness than average edge density, are not satisfactory. A graph G is d-degenerate
if every subgraph of G contains a vertex of degree at most d. In particular, this means (and, in
fact, degeneracy is equivalent to saying) that the average degree of every subgraph is bounded
by a constant. Observe that we can make every graph 2-degenerate by subdividing every edge
once (by subdividing an edge we mean the operation of replacing an edge {u, v} by a path of
length 2). Now it is easy to see that the Distance-2 Dominating Set problem on the class
of 2-degenerate graphs is just as hard as the Dominating Set problem on the class of all
graphs. Hence, in order to obtain a robust notion of sparseness, in particular, in a locality
sensitive setting as in distributed computing, we may want to require our notion of uniform
sparseness to be invariant under such local modifications. These requirements lead exactly to
the definition of classes of bounded expansion.
Dominating Set admits a constant factor approximation on bounded degree graphs, in
fact, it is complete for APX on these classes [53]. Hence under the assumption P 6= NP there
is no PTAS for the Dominating Set problem on bounded degree graphs. All the more so the
same holds for the more general Distance-r Dominating Set problem. However, for every
fixed value of r, there is a linear time computable constant factor approximation algorithm on
classes of graphs with bounded expansion [22] and these are the most general subgraph closed
classes on which a constant factor approximation algorithm for the Distance-r Dominating
Set problem is known.
Contribution 1. We present a new approximation algorithm for the Distance-r Dominating Set problem on classes of bounded expansion which improves the approximation
ratio achieved by the algorithm of [22]. Our algorithm can be implemented in linear time on
any class of bounded expansion. A key feature of our algorithm is that it is tailored to be
executed in a distributed setting.
There has been lots of effort to approximate the Dominating Set problem with distributed
algorithms, however, similar hardness results also apply to distributed algorithms. It was
shown in [38] that in t communication rounds the Dominating Set problem on an n-vertex
2
0
graphs of maximum degree ∆ can only be approximated within factor Ω(nc/t ) and Ω(∆c /t ),
where c and c0 are constants. This implies that, in general,
√ to achieve a constant approximation
ratio, every distributed algorithm requires at least Ω( log n) and Ω(log ∆) communication
rounds. Kuhn et al. [38] also provide the currently best approximation algorithm on general
graphs, which achieves a (1 + ε) ln ∆-approximation in O(log(n)/ε) rounds for any ε > 0.
For graphs of arboricity a there exists a forest decomposition algorithm achieving a factor O(a2 )-approximation in randomized time O(log n), and a deterministic O(a log ∆) approximation algorithm requiring O(log ∆) rounds [42]. Given any δ > 0, (1 + δ)-approximations of
a maximum independent set, of a maximum matching, and of a minimum dominating set can
be computed in O(log∗ n) rounds in planar graphs [17], which is asymptotically optimal [41].
It is easily seen that the algorithm of [17] extends to minor closed classes of graphs. A constant
factor approximation on planar graphs [40, 69] and on graphs of bounded genus [5] can be
computed locally in a constant number of communication rounds. In terms of lower bounds,
it was shown that there is no deterministic local algorithm (constant-time distributed graph
algorithm) that finds a (7 − ε)-approximation of a minimum dominating set on planar graphs,
for any positive constant ε [32].
Observe that all of the above algorithms cannot be directly employed to obtain good
approximations for the Distance-r Dominating Set problem, as all structural information
which is used in the algorithms may be lost when building the r-transitive closure of the graph.
The distributed algorithms of [39, 57] find distance-r dominating sets of size O(n/r) in time

3

O(r · log∗ n), without any relation to the size of an optimal distance-r dominating set. In very
restrictive settings, e.g., in trees [65] or in star-split graphs [68] better solutions are known.
The Distance-r Dominating Set problem is closely related to the problem of covering
local neighborhoods in a graph by connected clusters of small radius. The r-neighborhood of a
vertex v is the set Nr [v] of vertices w of distance at most r to v. An r-neighborhood cover [9]
is a set X of vertex sets X ⊆ V (G) such that for each vertex v ∈ V (G) there is a set X ∈ X
with Nr [v] ⊆ X. We are interested in covers of small radius, that is, rad(G[X]) shall be small
for all X ∈ X and small degree, that is, every vertex v ∈ V (G) shall lie in only a few clusters.
Sparse covers have many applications such as distance coordinates, routing with succinct
routing tables [2, 9], mobile user tracking [9], resource allocation [7], synchronisation in
distributed algorithms [8], and many more. Every graph admits an r-neighborhood cover
of radius at most 2r − 1 and degree at most 2r · n1/r [9] and asymptotically, this cannot
be improved in general [64]. Better covers are known to exist, e.g., for planar graphs [15]
and for classes that exclude a fixed minor [3]. In particular, the construction of [1] provides
r-neighborhood covers of radius O(t2 r) and degree 2O(t) · t! for graphs that exclude the
complete graph Kt as a minor. It follows from a construction in [29] that classes of bounded
expansion admit r-neighborhood covers of radius at most 2r and degree at most f (r) for some
function f depending on the class under consideration.
Contribution 2. We show that the algorithm of [29] for constructing sparse r-neighborhood
covers on classes of bounded expansion can be implemented in the CON GEST BC model of
distributed computing in O(r2 log n) communication rounds. Based on this construction, we
show that our newly proposed algorithm for the Distance-r Dominating Set problem
can be implemented in the CON GEST BC model in O(r2 log n) communication rounds on any
class of graphs of bounded expansion. Our result is based on a routing scheme presented by
Nešetřil and Ossona de Mendez in [51], which in turn is based on an iterative application of
an algorithm of Barenboim and Elkin [11].
While in a sequential setting one can trivially connect the vertices of a (distance-r) dominating set along a spanning tree to obtain a connected (distance-r) dominating set of small size,
creating such connections is a non-trivial task in the distributed setting. Several algorithms
were proposed to compute connected dominating sets in general graphs [19, 20, 59, 62, 70].
We also refer to these papers for applications of connected dominating sets for distributed
computing and routing. All lower bounds for the Dominating Set problem hold all the
more so for the Connected Dominating Set problem. In particular, none of the above
algorithms computes a constant factor approximation of a minimum connected dominating set
in a sub-linear number of communication rounds. To our knowledge, there is no distributed
algorithm to compute a constant factor approximation to the Connected (Distance-r)
Dominating Set problem on restricted graph classes.
Contribution 3. We show how to extend our algorithm for the Distance-r Dominating
Set problem to compute a constant factor approximation for the Connected Distance-r
Dominating Set problem. We hence prove that there exists a constant factor approximation
algorithm for the Connected Distance-r Dominating Set problem which works in the
CON GEST BC model in O(r2 log n) communication rounds on any class of graphs of bounded
expansion.
Finally, we show how to use the greater power of the LOCAL model to turn any distance-r
dominating set D into a connected distance-r dominating set of size at most c(r) · |D|, for

4

some small constant c(r) depending only on r and the class under consideration. This new
algorithm can be implemented in 3r + 1 communication rounds in the LOCAL model. In
combination with the algorithm of Lenzen et al. [40] we obtain a constant factor approximation
algorithm for the Connected Dominating Set problem on planar graphs in a constant
number of communication rounds in the LOCAL model (the constant c(1) which we need here
is 6). A similar result follows for graphs of bounded genus by combining our new algorithm
with an algorithm of [5].

2 Preliminaries
Graphs. In this paper, we consider finite, undirected simple graphs. For a graph G, we write
V (G) for the vertex set of G and E(G) for its edge set. A path of length ` in G is a subgraph
P ⊆ G with vertex set V (P ) = {v1 , . . . , v`+1 } and edge set E(P ) = {{vi , vi+1 } : 1 ≤ i < `}.
The path P connects its endpoints v1 and v`+1 . The distance between two vertices u, v ∈ V (G),
denoted dist(u, v), is the minimum length of a path that connects u and v or ∞ if no such
path exists. For v ∈ V (G), we write Nr [v] for the closed r-neighborhood of v, that is
Nr [v] = {u ∈ V (G) : dist(u, v) ≤ r}. Note that we allow paths
S of length 0, so Nr [v] always
contains v itself. For a set A ⊆ V (G), we write Nr [A] for v∈A Nr [v]. The radius of a
connected graph G is the minimum number rad(G) such that there is a vertex v ∈ V (G) with
Nrad(G) [v] = V (G).
~ on the same vertex set, which is denoted
An orientation of a graph G is a directed graph G
~ such that for each edge {u, v} ∈ E(G) the set of arcs E(G)
~ contains exactly one of the
V (G),
~
~
arcs (u, v) or (v, u). For v ∈ V (G), {u : (u, v) ∈ E(G)} is the set of the in-neighbours of v.
The indegree d− (v) of a vertex v is the number in-neighbours of v. We denote the maximum
~ by ∆− (G).
~ For any directed graph G
~ we denote the underlying undirected
indegree of G
graph by G.
The arboricity of a graph is the minimum number of spanning forests that partition its
edge set. The arboricity of a graph is within factor 2 of its degeneracy. For a set X ⊆ V (G)
we write G[X] for the subgraph of G induced by X. For k ∈ N, G is k-degenerate if for each
X ⊆ V (G) the graph G[X] contains a vertex of degree at most k. If an n-vertex graph G is
k-degenerate, then G contains at most k · n edges.
We assume that all graphs are represented by adjacency lists so that the total size of a
graph representation is linear in the number of edges and vertices.
~ of G with ∆− (G) ≤ k can be computed in time
If G is k-degenerate, then an orientation G
O(k · n) by a simple (sequential) greedy algorithm. Equivalently, we can order the vertices as
v1 , . . . , vn such that every vertex vi has at most k smaller neighbours vj1 , . . . , vjk , j` < i for
` ∈ {1, . . . , k}. In the same time complexity we can order all adjacency lists consistently with
the order. For the sequential model in Section 3 we assume that the identifiers of the vertices
occupy constant space while in the distributed model we assume log n-bit identifiers.
Distance -r dominating sets. For r ∈ N, a distance-r dominating set in a graph G is a
set M ⊆ V (G) such that Nr [M ] = V (G). A distance-1 dominating set is simply called a
dominating set.
Distributed system model. The clients of a network are modelled as the vertices V (G) of
a graph G, its communication links are represented by the edges E(G) of the graph. Each
client has a unique identifier (id) of size log n where n := |V (G)| is the order of the graph
known to every vertex. Communication is synchronous and reliable. In each round, each

5

vertex v ∈ V (G) may send a (different) message to each of its neighbors w ∈ N1 [v] (the vertex
specifies which message is sent to which neighbor) and receives all messages from its neighbors.
In the LOCAL model, messages may have arbitrary size, in the CON GEST model, messages
may have size O(log n). In the CON GEST BC model, every vertex may only broadcast the
same message of size O(log n) to all its neighbors. After sending and receiving messages, every
client may perform arbitrary finite computations. The complexity of a distributed algorithm
is its number of communication rounds. The network graph also represents the graph problem
that we are trying to solve, e.g., the Distance-r Dominating Set instance. At termination,
each vertex must output whether it is part of the distance-r dominating set or not, and these
outputs must define a valid solution of the problem. Note that every distributed algorithm
that runs in t rounds in We refer to [55] for more background.
Bounded expansion classes. A graph H with vertex set V (H) = {v1 , . . . , vn } is a minor
of G, written H 4 G, if there are pairwise disjoint connected subgraphs H1 , . . . , Hn of G,
called branch sets, such that if {vi , vj } ∈ E(H), then there are ui ∈ V (Hi ) and uj ∈ V (Hj )
with {ui , uj } ∈ E(G). We call (H1 , . . . , Hn ) a minor model of H in G. For r ∈ N, the graph
H is a depth-r minor of G, denoted H 4r G, if there is a minor model (H1 , . . . , Hn ) of H in
G such that each Hi has radius at most r. We write d(H) for the average degree of H, that
is, for the number 2|E(H)|/|V (H)|. A class C of graphs has bounded expansion if there is
a function f : N → N such that for all r ∈ N and all graphs H and G ∈ C, if H 4r G, then
d(H) ≤ f (r). The concept of bounded expansion as a model for uniform sparseness in graphs
was introduced by Nešetřil and Ossona de Mendez in [47, 48, 49]. Note that many familiar
sparse graph classes, such as planar graphs, bounded degree graphs, and graphs with excluded
(topological) minors have bounded expansion. For an extensive study of classes with bounded
expansion we refer the reader to [50]. Observe that every n-vertex graph from a bounded
expansion class is f (0)-degenerate and hence has at most f (0) · n many edges (depth-0 minors
of G are its subgraphs).
Generalized colouring numbers. Let G be a graph. A linear order L of V (G) is a reflexive,
anti-symmetric, transitive total binary relation L ⊆ V (G) × V (G). In the following, we will
write u ≤L v instead of (u, v) ∈ L. We write Π(G) for the set of all linear orders on V (G).
Let r ∈ N and let u, v ∈ V (G). Vertex u is weakly r-reachable from vertex v with respect to a
linear order L ∈ Π(G) if there exists a path P of length at most r between u and v such that
u is minimum among the vertices of P (with respect to L). Let WReachr [G, L, v] be the set of
vertices that are weakly r-reachable from v with respect to L. Note that v ∈ WReachr [G, L, v].
The weak r-colouring number wcolr (G) of G is defined as
wcolr (G) = min

max |WReachr [G, L, v]|.

L∈Π(G) v∈V (G)

The generalized colouring numbers were introduced by Kierstead and Yang in the context of
colouring games and marking games on graphs [36], and received much attention as a measure
for uniform sparseness in graphs, in particular, they can be used to characterize classes of
bounded expansion.
Theorem 1 (Zhu [71]). A class C of graphs has bounded expansion if and only if there is a
function f : N → N such that wcolr (G) ≤ f (r) for all r ∈ N.
Bounds for several restricted classes such as graphs of bounded tree-width, planar graphs
or graphs with excluded (topological) minors, were provided in [28, 37, 66].

6

Transitive fraternal augmentations. Let G be an undirected graph. For r ∈ N and an
~ r with edge
undirected graph G, a depth-r fraternal augmentation of G is a directed graph G
~ r ) partitioned as E1 ∪ . . . ∪ Er , such that
set E(G
~ r ), E1 ) is an orientation of G;
• the graph (V (G
~ r ) implies (v, u) 6∈ E(G
~ r ) for all u, v ∈ V (G
~ r );
• (u, v) ∈ E(G
• for all 1 ≤ i ≤ j ≤ r with i + j ≤ r, and for all u, v, w ∈SV (G) we have that (u, w) ∈ Ei
and (v, w) ∈ Ej implies that (u, v) or (v, u) belongs to i+j
k=1 Ek .
~ a depth-r transitive augmentation of G
~ is a graph G
~ tr obtained
For a directed graph G,
~ by adding all edges (u, v) such that there is a directed path of length at most r
from G
~ A depth-r transitive fraternal augmentation of G
~ is a depth-r transitive
between u and v in G.
~
augmentation of a depth-r fraternal augmentation of G.
Transitive fraternal augmentations were introduced in [47]1 . We refer also to Section 7.4 of
the textbook [50] for more background. We use low in-degree transitive fraternal augmentations
to approximate the weak coloring numbers. This approximation is based on the following
lemma, which is a simple variant of Lemma 5.7 of [29].
~ t be a depth-r transitive fraternal augmenLemma 2. Let G be a graph and let r ∈ N. Let G
r
−
t
t
~
~ tr . Let L be an
tation of G with ∆ (Gr ) ≤ d. Let Gr be the underlying undirected graph of G
order of V (Gtr ) such that every vertex has at most c smaller neighbors with respect to L. Then
|WReachr [G, L, v]| ≤ (d + 1)c + 1 for all v ∈ V (G).
Proof. Use Lemma 7.9 of [50] to show that if v1 . . . vk is a path of length at most r in G,
~ tr ) or (vk , v1 ) ∈ E(G
~ tr ) or there is some vi , 1 < i < k
then either v1 = vk or (v1 , vk ) ∈ E(G
t
~
such that (vi , v1 ), (vi , vk ) ∈ E(Gr ).
For each vertex v ∈ V (G) we count the number of end-vertices of paths of length at most r
from v such that the end-vertex is the smallest vertex of the path. This number is exactly
|WReachr [G, L, v)]|.
By our above observation, for each such path with end-vertex w =
6 v, we either have an
edge (v, w) or an edge (w, v) or there is u on the path and we have edges (u, v), (u, w) in
~ tr ). By assumption on L there are at most c edges (v, w) or (w, v) such that w <L v.
E(G
Furthermore, we have at most d edges (u, v), as v has in-degree at most d and for each such u
there are at most c edges (u, w) such that w <L u by assumption on L. These are exactly the
pairs of edges we have to consider, as no vertex on the path from v to w may be smaller than
w. Hence in total we have |WReachr [G, L, v]| ≤ c + d · c + 1 = (d + 1)c + 1.

As shown in [47], for every class C of bounded expansion there is a function d : N → N such
~ of G and a depth-r
that we can compute in linear time a depth-r fraternal augmentation G
t
−
t
~
~
~
~ tr ) ≤ d, then
transitive augmentation Gr of Gr such that ∆ (Gr ) ≤ d(r). Note that if ∆− (G
the underlying undirected graph Gtr is 2d-degenerate and hence we can compute an order
such that every vertex has at most 2d smaller neighbors in linear time.
Corollary 3. Let C be a class of bounded expansion. There is a linear time algorithm and a
function d : N → N which on input G ∈ C and r ∈ N computes in linear time a linear order of
V (G) witnessing that wcolr (G) ≤ d(r).
1

Note that in [47] transitive fraternal augmentations were defined by taking a depth-1 fraternal augmentation
and then a depth-1 transitive augmentation etc. for r times. Here, as in [51], the definition is changed to
work in the CON GEST BC model

7

Another possibility to approximate the weak coloring numbers in linear time is presented
in [22]. We remark that implicitly in that algorithm one also has to compute depth-r transitive
fraternal augmentations.
The next theorem shows that we can compute transitive fraternal augmentations, and
in fact also the weak colouring numbers, in the distributed setting in logarithmically many
rounds on graphs of bounded expansion.
Theorem 4 (Nešetřil and Ossona de Mendez in [51]). Let C be a class of bounded expansion and let r ∈ N. There are constants f (r) and F (r) such that one can compute for every
G ∈ C in O(r2 log n) communication rounds in the CON GEST BC model a depth-r transitive
~ t of G with ∆− (G
~ t ) ≤ f (r) and an order L of V (Gt ) such that every
fraternal augmentation G
r
r
r
vertex has at most F (r) smaller neighbors in Gtr with respect to L.
As the graph topology cannot be changed in the distributed setting, the algorithm simulates
the introduced fraternal edges by storing for each vertex v and each in-neighbor w in Ei a path
of length i such that routing along the paths is possible with small congestion. (Congestion is
the maximum number of paths containing the same vertex.) Routing along transitive edges is
realized via a broadcasting protocol. 2
The procedure described in Theorem 4 uses an algorithm by Barenboim and Elkin [11]
which computes an orientation of degenerate graphs. For this, we must assume that all vertices
know the order n of the input graph. The order is represented by assigning every vertex a
class-id, which together with the unique vertex-id induces a total order of V (G). We remark
that (though not explicitly stated) this order can be obtained as a by-product of the procedure
orient(z, C) described in [51, Section 4.4].
Corollary 5. Let C be a class of bounded expansion and let r ∈ N. There is a constant
d(r) such that one can compute for every G ∈ C in O(r2 log n) communication rounds in the
CON GEST BC model an order L of V (G) witnessing that wcolr (G) ≤ d(r).
Sparse neighborhood covers. Let G be a graph. For r ∈ N, an r-neighborhood cover of
G is a set X of subsets X ⊆ V (G), called the clusters of X , such that for each v ∈ V (G)
there is some X ∈ X with Nr (v) ⊆ X. The radius of X is the maximum radius of the graph
induced by a cluster X ∈ X . Note that in every r-neighborhood cover of bounded radius each
of the clusters induces a connected subgraph of G. The degree dX (v) of a vertex v ∈ V (G)
with respect to X is the number of clusters that contain v. The degree of X is the maximum
degree dX (v) over all vertices v ∈ V (G). The generalized colouring numbers can be used to
construct sparse neighborhood covers.
We fix a number r ∈ N for the remainder of the paper. For v ∈ V (G), let Xv be the set of
the vertices w such that v ∈ WReach2r [G, L, w].
Theorem 6 (Grohe et al. [29]). Let G be a graph and let c, r ∈ N. Let L be an order
witnessing that wcol2r (G) ≤ c. Then the collection X = {Xv : v ∈ V (G)} is an rneighborhood cover of G of radius 2r and degree c.
Hence, by combining Theorem 1 and Theorem 6, we obtain r-neighborhood covers of radius
at most r and degree at most f (r) for every class of bounded expansion. Classes that exclude
a fixed minor are the most general classes known to admit r-neighborhood covers of constant
degree (independent of r). Abraham et al. [3] have shown that if G excludes the complete
2

We remark that in [51] one actually computes 2r fraternal augmentations and r transitive augmentations,
to finally compute an r-centered coloring, which is not necessary in our case.

8

graph Kt as a minor, then there exists an r-neighborhood cover of radius O(t2 r) such that each
vertex belongs to at most 2O(t) t! clusters. The currently best known bounds for wcolr (G) if
Kt 64 G are from [66] and show that in this case wcolr (G) ∈ O(rt−1 ). Hence, using Theorem 6,
we obtain r-neighborhood covers of radius 2r and degree O((2r)t−1 ) for these graphs. Note
that the algorithms of [3, 66] to compute the neighborhood covers are inherently sequential.
We will show in Section 4 how to compute the r-neighborhood covers presented in Theorem 6
in a distributed setting.

3 Approximating distance -r dominating sets
Our first result shows how to (sequentially) compute good distance-r dominating sets in any
fixed class of bounded expansion. Our result improves the following result of Dvořák [22].
Theorem 7 (Dvořák [22]). For every class C of bounded expansion there is a function
c : N → N and a linear time algorithm which on input G ∈ C and r ∈ N computes an order
L ∈ Π(G) witnessing wcol2r (G) ≤ c(r) and a c(r)2 -approximation of a minimum distance-r
dominating set of G.
The remainder of this section is devoted to the proof of the following theorem.
Theorem 8. For every class C of bounded expansion there is a function c : N → N and a
linear time algorithm which on input G ∈ C and r ∈ N computes an order L ∈ Π(G) witnessing
wcol2r (G) ≤ c(r) and a c(r)-approximation of a minimum distance-r dominating set of G.
The constant c(r) in Theorem 8 is the same as in Theorem 7, hence we improve the currently
best known approximation constant from c2 to c.
Recall the definition of Xv (see Section 2):
Xv = {w ∈ V (G) : v ∈ WReach2r [G, L, w]} .

(1)

We define for a fixed vertex v ∈ V (G),
Rv := {w ∈ Xv : v = min WReachr [G, L, w]} .
Lemma 9. For all v ∈ V (G) and for all w ∈ Rv we have Nr [w] ⊆ Xv .
Proof. Let w ∈ Rv . Observe first that v is the minimum element in Nr [w]. Now let
u ∈ Nr [w]. Then there is a path of length at most r from u to w with all vertices in Nr [w]
and a path of length at most r from w to v again with all vertices in Nr [w]. Hence there is a
path of length at most 2r from u to v with all vertices in Nr [w]. As v is minimal in Nr [w],
this path witnesses that v ∈ WReach2r [G, L, u], and hence by definition of Xv it holds that
u ∈ Xv .

Proof. (of Theorem 8) We claim that the set
D := {min WReachr [G, L, w] : w ∈ V (G)} = {v ∈ V (G) : Rv 6= ∅}

(2)

is a c-approximation of a minimum distance-r dominating set. Obviously, D is a distance-r
dominating set of V (G), as every vertex w is dominated by min WReachr [G, L, w]. It remains
to show that we achieve the claimed approximation ratio.

9

For v ∈ V (G), let Xv and Rv be as above. Let X be the collection {Xv : v ∈ V (G)} as in
Theorem 6. Then X is an r-neighborhood cover of degree c and by Lemma 9, for w ∈ Rv , we
have Nr [w] ⊆ Xv .
Let M be a minimum distance-r dominating set in G. As every w ∈ V (G) can be distance-r
dominated only from Nr [w] ⊆ Xv , it follows that if w ∈ Rv , then M ∩ Xv 6= ∅.
Hence, as every vertex appears in at most c clusters, it holds that
[
X
|D| = |
{v}| ≤
|M ∩ Xv | ≤ c · |M |.
v∈V (G)

v∈V (G)

Rv 6=∅

Rv 6=∅

We finally show how to compute D in linear time. We assume that G is stored in memory
by n adjacency lists. We first use the linear time approximation algorithm for the weak
coloring numbers from Corollary 3 to compute an order L, which will be represented in a way
such that one can iterate through the vertices along L in O(|V (G)|) time and such that a
comparison u <L w for every pair u, w ∈ V (G) takes O(1) time. Here we assume that vertices
are equipped with constant size identifiers representing the order. The algorithm is given as
Algorithm 1.
Algorithm 1 DomSet(G, L)
Input: Graph V (G); V (G) = {vi : 1 ≤ i ≤ n}; vi <L vj for i < j; A(vi ) is the adjacency list
of vi
Output: A c-approximation of a dominating set of G
1: SortLists(L)
. Algorithm 2
2: D ← ∅
3: Dominated ← ∅
4: for i ← 1, . . . , n do
5:
Ni ←BFS(vi , L)
. Algorithm 3
6:
if Ni \ Dominated 6= ∅ then
7:
D ← D ∪ {vi }
8:
Dominated ← Dominated ∪ Ni
9: return D
In the first step (Line 1 of Algorithm 1 and Algorithm 2), we ensure in linear time that
every adjacency list is sorted increasingly with respect to L. Algorithm 2 iterates through the
vertices of G in order L starting from the least vertex (such that the next vertex can always
be found in constant time) and thus has running time O(m). As graphs of bounded expansion
are degenerate, we have m ∈ O(n).
Algorithm 2 SortLists(L)
Input: Graph V (G); V (G) = {vi : 1 ≤ i ≤ n}; vi <L vj for i < j; A(vi ) is the adjacency list
of vi
Output: A(vi ) is increasingly sorted with respect to L
1: for i ← 1, . . . , n do B(vi ) ← A(vi ) and A(vi ) ← ()
2: for i ← 1, . . . , n do
3:
for vj ∈ B(vi ) do
4:
add vi at the end of A(vj )
Now Algorithm 1 iterates through the vertices of G starting with the least element v1 along
L. For every vi ∈ V (G), it uses Algorithm 3 to compute the set of vertices that are bigger

10

than vi and are dominated by vi . If such a vertex is not dominated by a vertex smaller than
vi , it serves as a vertex w in the definition of D (see (2)). Indeed, vi ∈ WReachr [G, L, w]
because w was found by a breadth-first search from v restricted to vertices greater than v
with respect to L and to distances at most r. On the other hand, if not v was the minimum
vertex in WReachr [G, L, w] but, say, u, then w would be dominated by u and added to the
set Dominated in the earlier iteration j for u = vj . Thus vi = min WReachr [G, L, w] and vi
is added to D.
Algorithm 3 BFS(v, L, r)
. As usual BFS, but restricted to vertices w >L v and only for r steps.
Input: Graph G; for w ∈ V (G), the adjacency list A(w) is increasingly sorted w.r.t. to L
1: Q ← empty queue
2: Enqueue (v, 0) in Q
3: while Q 6= ∅ do
4:
(w, dist) ← dequeue from Q
5:
if dist < r then
6:
for u ∈ A(w) and u >L v do
7:
if u not marked as visited then
8:
mark u as visited
9:
enqueue (u, dist + 1) in Q
10: return marked vertices

Let us estimate the running time of Algorithm 1. Recall that Line 1 has linear running
time. Note that every set Ni computed in Line 5 for a vertex vi is a subset of Xvi because
Algorithm 3 restricts its search to vertices bigger than vi and to distances at most r. That
is, if w ∈ Nvi , then vi ∈ WReachr [G, L, w] ⊆ WReach2r [G, L, w] and thus w ∈ Xvi . As
every graph G ∈ C is c-degenerate, every induced subgraph H ⊆ G has at most c · |V (H)|
many edges, also the graph induced by Ni . When constructing Ni in Algorithm 3 we will
only visit vertices of Ni and, for every w ∈ Ni at most one vertex in its adjacency list
that is not in Ni . This can be achieved if Line 6 of Algorithm 3 is implemented as an
iteration through A(w) starting from the biggest vertex and stopping if a vertex u ∈ A(w)
with u <L w is reached (recall that A(w) sorted). Hence this search requires time at most
O((c + 1) · |Nvi |) =P
O(c · |Xvi |). As every vertex w appears in at most c clusters Xv , we obtain
a running time of v∈V (G) O(c · |Xv |) = O(c2 · n).
Note that by Theorem 1 the constant c(r) in the theorem exists for every class of bounded
expansion. Besides the improved approximation ratio, our algorithm is simpler than that
of [22]. In particular, given an order L ∈ Π(G), it can straightforwardly be implemented in a
distributed way.
Remark 10. Algorithm 3 with parameters v, L and 2r computes Xv in time O(c · |Xv |).

4 Distributed r -neighborhood covers and r -dominating sets
In this section we will show how to compute sparse r-neighborhood covers as described in
Theorem 6 and the Distance-r Dominating Set of Theorem 8 in a distributed setting.
In order to compute r-neighborhood covers according to Theorem 6, we want to compute
an order L of V (G) which witnesses that wcol2r (G) ≤ c. In the distributed setting, that

11

means that every vertex w learns its weak reachability set WReach2r [G, L, w] and, for each
v ∈ WReach2r [G, L, w], a path within Xv of length at most 2r from w to v.
In order to find the distance-r dominating set described in Theorem 8, every vertex w will
choose min WReachr [G, L, w] as its dominator and send a message to that vertex along the
stored path. (Note that we computed the order L for the parameter 2r, but are using it for
r.) Even if all vertices send their messages at once, no vertex will have to forward more than
c messages.
First, using Corollary 5, we compute for a given graph G an order L witnessing that
wcol2r (G) ≤ c(2r) in O(r2 log n) communication rounds. We show that every vertex can learn
its weak reachability set as well as a routing scheme which preserves short distances. Recall
from (1) that Xv is defined as Xv = {w ∈ V (G) : v ∈ WReach2r [G, L, w]}. The proof can be
found in .
Lemma 11. Let C be a class of bounded expansion and let r ∈ N. There is a constant c = c(2r)
such that for every G ∈ C there is a linear order L on V (G) such that |WReach2r [G, L, w]| ≤ c
for all w ∈ V (G) and in O(r2 · log n) communication rounds every vertex w can learn
WReach2r [G, L, w] and for each v ∈ WReach2r [G, L, w] a path Pv,w of length at most 2r
from w to v, which is a shortest path between v and w in the graph induced by Xv . In
particular, if v = min WReachr [G, L, w], then the path Pv,w is a shortest path between v and w
in G.
Proof. Lemma 11. Let C be a class of bounded expansion and let r ∈ N. There is a
constant c = c(2r) such that for every G ∈ C there is a linear order L on V (G) such that
|WReach2r [G, L, w]| ≤ c for all w ∈ V (G) and in O(r2 · log n) communication rounds (in
CON GEST BC ) every vertex w can learn WReach2r [G, L, w] and for each v ∈ WReach2r [G, L, w]
a path Pv,w of length at most 2r from w to v, which is a shortest path between v and w in
the graph induced by Xv . In particular, if v = min WReachr [G, L, w], then the path Pv,w is a
shortest path between v and w in G.
Proof. The pseudocode is given in Algorithm 4. First, using Corollary 5, we compute for a
given graph G an order L witnessing that wcol2r (G) ≤ c(2r) in O(r2 log n) communication
rounds.
The procedure implicitly uses an algorithm of Barenboim and Elkin [11], which assigns to
each vertex v a class id cl(v), which together with the unique vertex identifier induces the
linear order L. For ease of presentation, we write vi for the vertex at position i in the order L
and call i the super-id of the vertex.
The remaining part of the computation has 2r rounds which correspond to 2r rounds of a
breadth-first search as in Algorithm 3. This time, the search is performed in parallel and we
have to make sure that only a logarithmic amount of information is sent by every vertex for
the CON GEST BC model. The idea is that every vertex w forwards only information about
paths that start in a vertex v ∈ WReach2r [G, L, w].
Every vertex w maintains a set Pw of paths of length at most 2r from vertices v ∈
WReach2r [G, L, w]. For every vertex v 6= w there is at most one path Pv in Pw that starts
in v and certifies that v ∈ WReach2r [G, L, w]. In the first round, every vertex broadcasts its
super-id, which we understand as a path of length 0. A vertex w receives super-ids and stores
only those which are smaller than its own super-id.
In a later iteration, every vertex w receives some sets of paths from its neighbors and
computes their union P. For every vertex u1 , with a super-id greater than the super-id of w,

12

Algorithm 4 WReachDist(r)
Input (for a vertex w): n = |V (G)|, adjacency list of w, id of w
Output: WReach2r [G, L, w], min WReachr [G, L, w] for a particular linear order L (see text)
1: in parallel, compute L
. by Corollary 5
. when done, every vertex w knows its super-id sid(w)

2: in parallel, Pw = {sid(w)}
3: for i = 1, . . . , r do
4:
in parallel, broadcast Pw , receive new paths in P
5:
in parallel (for vertex w):
6:
toSend ← ∅
7:
for u1 first vertex in a path from P do
8:
if sid(u1 ) < sid(w) then
9:
P ← shortest path from P ∪ Pw that starts in u1 , break ties using super-ids
10:
if exists P 0 ∈ Pw with P 0 = u1 , . . . then
11:
remove P 0 from Pw
12:
Pw ← Pw ∪ {P }
13:
toSend ← toSend ∪ {u1 , . . . , uj , w}
. where P = u1 , . . . , uj .
14:

broadcast the set toSend

all paths from P starting in u1 are discarded. For every vertex u1 with a smaller super-id,
vertex w selects the shortest path starting in u1 among all paths in P and Pw . (There is at
most one path in Pw that starts in u1 .) If there are many such shortest paths, w chooses the
lexicographically least one (with respect to the super-ids). Let this path be P = u1 , . . . , uj
for some j ≤ 2r. Then P is stored in Pw (if there is already a path in Pw that starts in u1 , it
is replaced by P ). If j < 2r, then w broadcasts the path u1 , . . . , uj , w.
Observe that every vertex w forwards information about a vertex v only if v ∈ WReach2r [G, L, w].
Hence, w forwards only at most c paths simultaneously and the whole procedure works in
the CON GEST BC model. Observe also that we perform a breadth-first search through the
cluster Xv and break ties according to the order by vertex super-ids. This implies our claims
on shortest paths.

We can now combine Theorem 6 and Lemma 11 to obtain the first main theorem of this
section.
Theorem 12. Let C be a class of bounded expansion. There is a distributed algorithm which
for every graph G ∈ C and every r ∈ N computes a representation of a sparse r-neighborhood
cover in the CON GEST BC model in O(r2 · log n) communication rounds. More precisely, the
algorithm computes an order L, represented by log n-sized labels and for every vertex v a
routing scheme of length at most 2r to every vertex in WReach2r [G, L, v].
Also Theorem 8 can now be implemented as a distributed algorithm.
Theorem 13. Let C be a class of bounded expansion and let r ∈ N. There is a constant c and
a distributed algorithm which for every graph G ∈ C computes a c-approximation of a minimum
distance-r dominating set in the CON GEST BC model in O(r2 · log n) communication rounds.
Proof. Recall that we want to compute the distance-r dominating set
D := {v ∈ V (G) : v = min WReachr [G, L, w] for some w ∈ V (G)},

13

that is, every vertex w elects the smallest vertex from its r-neighborhood with respect to L to
the distance-r dominating set. As w knows WReachr [G, L, w] and a routing scheme to these
vertices, all vertices can send to the smallest vertex in the list a short message that it should
be included in the dominating set. Observe that if a vertex u has to forward the identifier
of a vertex w ∈ WReachr [G, L, v] from some other vertex v, then also w ∈ WReachr [G, L, u].
Hence, no vertex has to forward more than c messages of total size at most O(c · log n). 

5 Connected Dominating Sets
In this section we study the Connected Distance-r Dominating Set problem. Our main
result in this section is the following theorem.
Theorem 14. Let C be a class of bounded expansion and let r ∈ N. There is a constant c
and a distributed algorithm which for every graph G ∈ C computes a c-approximation of a
minimum connected distance-r dominating set in the CON GEST BC model in O(r2 · log n)
communication rounds.
The following observation is folklore, we provide a proof for completeness.
Lemma 15. Let G be a connected graph and let D be a distance-r dominating set of G. Let
P be a set of paths in G such that for each pair u, v ∈ D with dist(u, v) ≤ 2r
S + 1 there is
a path Pu,v ∈ P connecting u and v. Then the subgraph H induced by D ∪ P ∈P V (P ) is
connected.
Proof. We show by induction on dist(u, v) that all u, v ∈ D are connected in H. The claim
holds by definition of H if dist(u, v) ≤ 2r + 1. Now assume that dist(u, v) ≥ 2r + 2 and let
P = (u = v0 , v1 , . . . , vt = v) with t ≥ 2r + 3 be a shortest path connecting u and v. As P is a
shortest path, neither u nor v dominate vr+1 . Hence there is another vertex w ∈ D which
dominates vr+1 . As v1 and vr+1 are connected by a path of length r, and w and vr+1 are
connected by a path (w = w0 , w1 , . . . , wr0 = vr+1 ) of length r0 ≤ r, dist(u, w) ≤ 2r, hence w
and u are connected in H. Furthermore, the path P 0 = (w, w1 , . . . , wr0 −1 , vr+1 , . . . , vt = v) is
shorter than P , hence, by induction hypothesis, w and v are connected in H. This implies
that u, v are connected in H.

Now, we use the local separation properties of the weak colouring numbers to connect the
dominating set we computed in Theorem 13. The proof of the following lemma is immediate
by definition of weak reachability.
Lemma 16. Let G be a graph and let L be a linear order on V (G). Let u, v ∈ V (G) be such
that there exists a path P between u and v of length at most r. Let w be the minimal vertex of
P with respect to L. Then w ∈ WReachr [G, L, u] and w ∈ WReachr [G, L, v].
Corollary 17. Let G be a connected graph and let L be a linear order on V (G). Let D be an
r-dominating set of G. Let D0 be a set which is obtained by adding for each v ∈ D and each
w ∈ WReach2r+1 [G, L, v] the vertex set of a path between v and w. Then D0 is a connected
distance-r dominating set of G.
Proof. Fix a set P of paths in G such that for each pair u, v ∈ D with dist(u, v) ≤ 2r + 1
there is a pathSPu,v ∈ P connecting u and v. According to Lemma 15, the subgraph H
induced by D ∪ P ∈P V (P ) is connected. According to Lemma 16, for each path Pu,v between

14

u and v, there is a vertex w ∈ V (Pu,v ) is weakly 2r + 1-reachable both from u and from v.
As D0 contains the vertex set of a path between u and w and of a path between v and w, it
follows that D0 is a connected distance-r dominating set of G.

We are now ready to prove the main theorem.
Proof. (of Theorem 14) Instead of computing an order L for wcol2r (G) as in Theorem 13,
we compute an order L for wcol2r+1 (G). Assume |WReach2r+1 [G, L, v]| ≤ c0 for all v ∈ V (G).
We compute an r-dominating set D based on the order L. Note that in Section 4 we used L
computed for parameter 2r and now we use L computed for 2r + 1, but for all orders L and
all v ∈ V (G) we have |WReach2r [G, L, v]| ≤ |WReach2r+1 [G, L, v]|.
By Theorem 8, D is at most c0 times larger than a minimum distance-r dominating set. As
a by-product, see Lemma 11, every vertex v learns a path of length at most 2r + 1 to each
w ∈ WReach2r+1 [G, L, v]. Now, every vertex broadcasts its set of paths to construct the set
D0 . As in the proof of Theorem 13, observe that if a vertex x has to forward a path from
w ∈ WReachr [G, L, v] to v for some other vertex v, then also w ∈ WReachr [G, L, x]. Hence,
no vertex has to forward more than c0 messages of total size at most O(c0 · r · log n). Clearly,
the computed set D0 has size at most c0 · (2r + 1) · |D| and by Corollary 17 it is a connected
distance-r dominating set. We conclude be defining c := c02 · (2r + 1).

We now show how to use the greater power of the LOCAL model to compute connected
dominating sets with much smaller constants involved. Our theorem is based on the simple
observation that in the LOCAL model we can construct for every connected graph from an
r-dominating set D a connected depth-r minor with |D| vertices. This minor (by definition of
bounded expansion classes) has only a linear number of edges and we can hence choose a set
of short paths realizing the corresponding connections to connect the dominating set.
We want to define a partition of V (G) into balls around vertices from an r-dominating
set D. For a connected graph G and an injection id : V (G) → N, we define the lexicographic
order <lex on the set of paths in V (G) with respect to id as follows. Consider two paths
P1 = v1 , . . . , vk and P2 = w1 , . . . , w` . If k < `, then P ≤lex P2 . If k = `, then P1 ≤lex P2 if the
sequence id(v1 ), . . . , id(vk ) is lexicographically smaller than the sequence id(w1 ), . . . , id(w` )
or P1 = P2 . For vertices v, w ∈ V (G), let P (v, w) be the lexicographically shortest path from
v to w.
Let G be a connected graph, let id(v) be the unique identifier of v and let D be a distance-r
dominating set of G. For each v ∈ D let
B(v) := {w ∈ V (G) : P (v, w) ≤lex P (u, w) for all u ∈ D, u 6= v} .
The D-partition B(D) of G with respect to id is the set {B(v) : v ∈ D}.
The proofs of the following two lemmas can be found in ??.
Lemma 18. Let G be a connected graph and let D be a distance-r dominating set of G. Then
B(D) = {B(v) : v ∈ D} is a partition of V (G) and G[B(v)] has radius at most r for all
v ∈ D.
Proof. As G is connected and D is a distance-r dominating set, B is a partition of V (G).
Furthermore, for each w ∈ V (v), there is a lexicographically shortest path P of length at
most r from v to w in G. Assume towards a contradiction that P is not also a path in
B(v). Then there is z ∈ V (P ) and u ∈ D such that z ∈ B(u). By definition of B(u), the
lexicographically shortest path Q0 from u to z is smaller than the lexicographically shortest
path Q between v and z. But then the path P 0 obtained by replacing the initial part Q of P
by Q0 is lexicographically smaller than P , a contradiction.


15

Lemma 19. Let G be a connected graph and let D be a distance-r dominating set of G. By
contracting the sets B(v) for v ∈ D, we obtain a connected depth-r minor of G.
Proof. It is immediate by definition of depth-r minors and Lemma 18 that we construct a
depth-r minor H 4r G. Furthermore, as G is connected and as B(D) is a partition of V (G)
by the same lemma, it is easy to see that H is connected.

Lemma 20. Let G be a connected graph such that for each depth-r minor H 4r G we have
|E(H)| ≤ d · |V (H)|. Let D be a distance-r dominating set of G. We can compute a connected
dominating set D0 of size at most 2r · d · |D| in 3r + 1 communication rounds in the LOCAL
model.
Proof. In this proof, we write H(D) for the depth-r minor constructed from a distance-r
dominating set D as in Lemma 19.
Every vertex v ∈ D can find its 2r + 1-neighborhood in 2r + 1 communication rounds. With
this information, each v ∈ D can construct B(v), as all possible dominators for w ∈ Nr [v]
must come from N2r [v]. Each vertex v ∈ D (now understood as representing a vertex of
H(D)) can also learn its neighbors in H(D) (here we need to learn N2r+1 [v]). Now each
vertex v computes the lexicographically shortest path Puv of length at most 2r + 1 for each
neighbor u in H(D) (take the ordering induced by vertex id’s). Observe that u and v fix
the same path Pvu , hence, the two vertices can report to all vertices on Pvu in another r
communication rounds that they shall be included in the connected dominating set D0 .
By Lemma 19, the constructed set D0 is a connected distance-r dominating set. Furthermore,
by assumption, H(D) has at most d · |D| many edges. Each edge is replaced by at most 2r − 1
vertices in the above construction. Adding the |D| vertices of the original set D, we obtain
the claimed bounds.

As a corollary from Lemma 18 and Lemma 20 we obtain the following theorem.
Theorem 21. Let C be a class of graphs of bounded expansion and assume that for every
graph G ∈ C we can compute a c-approximation D of a minimum distance-r dominating set of
G in t rounds in the LOCAL model. Let f : N → N denote the edge density function of depth-r
minors of C. Then there is a distributed algorithm which finds a 2rcf (r)-approximation for
connected distance-r dominating set of G in O(t + r) rounds in the LOCAL model.
The theorem can be applied, e.g., to extend the algorithm of Lenzen et al. [40] to obtain a
connected dominating set on planar graphs in the local model which is only 6 times larger
than the dominating set computed for the planar graph (an n-vertex planar graph has at
most 3n − 6 edges). Similarly, it applies to the extension of Lenzen et al.’s algorithm by Amiri
et al. [5] for graphs of bounded genus or to the randomized O(a2 ) approximation of Lenzen
and Wattenhofer [42] applied to graphs with excluded minors (here, a ∈ O(t log t) if Kt is
excluded as a minor).

References
[1] Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops,
robbers, and threatening skeletons: padded decomposition for minor-free graphs. In
Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June
03, 2014, pages 79–88, 2014.

16

[2] Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding
a fixed minor. In International Symposium on Distributed Computing, pages 442–456.
Springer, 2005.
[3] Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-diameter decompositions of minor free graphs. In Proceedings of the nineteenth annual ACM symposium
on Parallel algorithms and architectures, pages 16–24. ACM, 2007.
[4] Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for
k-restrictions. ACM Transactions on Algorithms (TALG), 2(2):153–177, 2006.
[5] Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. A local constant
factor MDS approximation for bounded genus graphs. In Proceedings of the 2016 ACM
Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA,
July 25-28, 2016, pages 227–233, 2016.
[6] Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications.
Combinatorica, 23(3):365–426, 2003.
[7] Baruch Awerbuch and David Peleg. Locality-sensitive resource allocation. Citeseer, 1990.
[8] Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium
on, pages 514–522. IEEE, 1990.
[9] Baruch Awerbuch and David Peleg. Sparse partitions. In Foundations of Computer
Science, 1990. Proceedings., 31st Annual Symposium on, pages 503–513. IEEE, 1990.
[10] Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs.
Journal of the ACM (JACM), 41(1):153–180, 1994.
[11] Leonid Barenboim and Michael Elkin. Sublogarithmic distributed mis algorithm for sparse
graphs using Nash-Williams decomposition. Distributed Computing, 22(5-6):363–379,
2010.
[12] Judit Barilan, Guy Kortsarz, and David Peleg. How to allocate network centers. Journal
of Algorithms, 15(3):385–415, 1993.
[13] M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient multi-prover interactive
proofs with applications to approximation problems. In Proc. 25th ACM Symp. on Theory
of Computing, volume 113, page 131, 1993.
[14] Dimitri P. Bertsekas, Robert G. Gallager, and Pierre Humblet. Data networks, volume 2.
Prentice-Hall International New Jersey, 1992.
[15] Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Improved sparse covers for
graphs excluding a fixed minor. In Proceedings of the twenty-sixth annual ACM symposium
on Principles of distributed computing, pages 61–70. ACM, 2007.
[16] Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations
research, 4(3):233–235, 1979.

17

[17] 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.
[18] Fei Dai and Jie Wu. An extended localized algorithm for connected dominating set
formation in ad hoc wireless networks. IEEE transactions on parallel and distributed
systems, 15(10):908–920, 2004.
[19] Bevan Das and Vaduvur Bharghavan. Routing in ad-hoc networks using minimum
connected dominating sets. In Communications, 1997. ICC’97 Montreal, Towards the
Knowledge Millennium. 1997 IEEE International Conference on, volume 1, pages 376–380.
IEEE, 1997.
[20] Bevan Das, Raghupathy Sivakumar, and Vaduvur Bharghavan. Routing in ad hoc
networks using a spine. In Computer Communications and Networks, 1997. Proceedings.,
Sixth International Conference on, pages 34–39. IEEE, 1997.
[21] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings
of the 46th Annual ACM Symposium on Theory of Computing, pages 624–633. ACM,
2014.
[22] Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse
graphs. European Journal of Combinatorics, 34(5):833–840, 2013.
[23] David Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica,
27(3-4):275–291, 2000.
[24] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM),
45(4):634–652, 1998.
[25] Michael R. Garey and David S. Johnson. Computers and intractability: a guide to the
theory of NP-completeness. WH Free. Co., San Fr, 1979.
[26] Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating
sets in planar graphs with applications. In International Workshop on Graph-Theoretic
Concepts in Computer Science, pages 201–216. Springer, 2001.
[27] Martin Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica, 23(4):613–632, 2003.
[28] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Colouring and covering nowhere dense graphs. In Graph-Theoretic
Concepts in Computer Science - 41st International Workshop, WG 2015, Garching,
Germany, June 17-19, 2015, Revised Papers, pages 325–338, 2015.
[29] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties
of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory
of Computing, pages 89–98. ACM, 2014.
[30] Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion
and low-density graphs. In Algorithms-ESA 2015, pages 717–728. Springer, 2015.
[31] Alan R. Hevner and Aruna Rao. Distributed data allocation strategies. Advances in
Computers, 27:121–155, 1988.

18

[32] Miikka Hilke, Christoph Lenzen, and Jukka Suomela. Brief announcement: Local
approximability of minimum dominating set on planar graphs. In Proceedings of the 2014
ACM symposium on Principles of distributed computing, pages 344–346. ACM, 2014.
[33] David S Johnson. Approximation algorithms for combinatorial problems. Journal of
computer and system sciences, 9(3):256–278, 1974.
[34] Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis,
Royal Institute of Technology Stockholm, 1992.
[35] Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer
computations, pages 85–103. Springer, 1972.
[36] Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number.
Order, 20(3):255–264, 2003.
[37] Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The
generalised colouring numbers on classes of bounded expansion. In 41st International
Symposium on Mathematical Foundations of Computer Science, MFCS, pages 85:1–85:13,
2016.
[38] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower
and upper bounds. arXiv preprint arXiv:1011.5470, 2010.
[39] Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and
applications. In Proceedings of the fourteenth annual ACM symposium on Principles of
distributed computing, pages 238–251. ACM, 1995.
[40] 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.
[41] Christoph Lenzen and Roger Wattenhofer. Leveraging linial’s locality limit. In International Symposium on Distributed Computing, pages 394–407. Springer, 2008.
[42] Christoph Lenzen and Roger Wattenhofer. Minimum dominating set approximation in
graphs of bounded arboricity. In International Symposium on Distributed Computing,
pages 510–524. Springer, 2010.
[43] László Lovász. On the ratio of optimal integral and fractional covers. Discrete mathematics,
13(4):383–390, 1975.
[44] Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization
problems. Journal of the ACM (JACM), 41(5):960–981, 1994.
[45] Howard L Morgan and K Dan Levin. Optimal program and data locations in computer
networks. Communications of the ACM, 20(5):315–322, 1977.
[46] Kowtha Murthy, John Kam, and MS Krishnamoorthy. An approximation algorithm
to the file allocation problem in computer networks. In Proceedings of the 2nd ACM
SIGACT-SIGMOD symposium on Principles of database systems, pages 258–266. ACM,
1983.

19

[47] Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded
expansion I. Decompositions. European Journal of Combinatorics, 29(3):760–776, 2008.
[48] Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded
expansion II. algorithmic aspects. European Journal of Combinatorics, 29(3):777–791,
2008.
[49] Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion III. restricted graph homomorphism dualities. European Journal of Combinatorics,
29(4):1012–1024, 2008.
[50] Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity. Springer, 2012.
[51] Jaroslav Nešetřil and Patrice Ossona de Mendez. A distributed low tree-depth decomposition algorithm for bounded expansion classes. Distributed Computing, 29(1):39–49,
2016.
[52] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood. Characterizations and
examples of graph classes with bounded expansion. European Journal of Combinatorics,
33(3):350–373, 2012.
[53] Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and
complexity classes. In Proceedings of the twentieth annual ACM symposium on Theory of
computing, pages 229–234. ACM, 1988.
[54] David Peleg. Distributed data structures: a complexity-oriented view. In International
Workshop on Distributed Algorithms, pages 71–89. Springer, 1990.
[55] David Peleg. Distributed computing: a locality sensitive approach. SIAM Monographs
on discrete mathematics and applications, 5, 2000.
[56] David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables.
Journal of the ACM (JACM), 36(3):510–530, 1989.
[57] Lucia D. Penso and Valmir C. Barbosa. A distributed algorithm to find k-dominating
sets. Discrete Applied Mathematics, 141(1):243–253, 2004.
[58] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a subconstant error-probability pcp characterization of np. In Proceedings of the twenty-ninth
annual ACM symposium on Theory of computing, pages 475–484. ACM, 1997.
[59] R. Sivakumar, B. Das, and V. Bharghavan. An improved spine-based infrastructure for
routing in ad hoc networks. In IEEE Symposium on Computers and Communications,
volume 98, 1998.
[60] Petr Slavík. A tight analysis of the greedy algorithm for set cover. In Proceedings of the
twenty-eighth annual ACM symposium on Theory of computing, pages 435–441. ACM,
1996.
[61] Aravind Srinivasan. Improved approximation guarantees for packing and covering integer
programs. SIAM Journal on Computing, 29(2):648–670, 1999.

20

[62] Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic. Dominating sets and neighbor
elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on
parallel and distributed systems, 13(1):14–25, 2002.
[63] Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24,
2013.
[64] Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM
(JACM), 52(1):1–24, 2005.
[65] Volker Turau and Sven Köhler. A distributed algorithm for minimum distance-k domination in trees. Journal of Graph Algorithms and Applications, 19(1):223–242, 2015.
[66] Jan van den Heuvel, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian
Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor.
European Journal of Combinatorics, Selected Papers of EuroComb’15, 2016 (to appear).
[67] Peng-Jun Wan, Khaled M. Alzoubi, and Ophir Frieder. Distributed construction of
connected dominating set in wireless ad hoc networks. In INFOCOM 2002. Twenty-First
annual joint conference of the IEEE computer and communications societies. Proceedings.
IEEE, volume 3, pages 1597–1604. IEEE, 2002.
[68] Fu-Hsing Wang, Jou-Ming Chang, Yue-Li Wang, and Sun-Jen Huang. Distributed
algorithms for finding the unique minimum distance dominating set in directed split-stars.
Journal of Parallel and Distributed Computing, 63(4):481–487, 2003.
[69] 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.
[70] Jie Wu and Hailan Li. On calculating connected dominating set for efficient routing in
ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete
algorithms and methods for mobile computing and communications, pages 7–14. ACM,
1999.
[71] Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete
Mathematics, 309(18):5562–5568, 2009.

21

