on unit disk graphs and on general graphs. In [17], we have shown that on general graphs, approximating minimum frac- tional dominating set up to a constant factor needs time at least Ω(^{p}log n/ log log n). The fact that in the given unit disk graph model, we can compute a constant approximation in a single communication round shows that there can be a large gap between the distributed complexity of problems on the unit disk graph and on general graphs.

5.

# NETWORK DECOMPOSITION

In the last section, we have seen that in the unit disk graph, knowing the distances to direct neighbors is enough to reasonably approximate important problems such as min- imum dominating set in just one round or a constant num- ber of rounds. If we want to compute more sophisticated structures such as a maximal independent set or even a (O(1), O(1))-decomposition, the methods of Section 4 can- not be used. It is in fact not hard to see that it is not even possible to construct a MIS or a decomposition in a constant number or rounds. In [20], Linial proved that computing a MIS on a ring needs at least Ω(log^{∗ }n) rounds. Because a ring where all edges have length 1 is a unit disk graph, this lower bound applies to our model. Note that it does not help to know the edge lengths if all edges have length 1. In this section, we will show that in the model of Section 4, it is indeed possible to compute a (O(1), O(1))-decomposition in O(log^{∗ }n) rounds. Our result even holds in a more general model where nodes can “live” in an arbitrary metric space instead of the Euclidean plane as in the UDG model. Anal- ogously to the UDG model, we define the unit ball graph where two nodes are connected by an edge if and only if their distance is at most 1. Our result also applies in dif- ferent related models where e.g. the distance between two nodes reflects the propagation delay of messages between the two nodes. The quality of the network decomposition that we achieve depends on the doubling dimension of the underlying metric.

5.1

# Basic Algorithm

In this section, we will now first present a (potentially slow) deterministic distributed algorithm which computs a (2, O(1))-decomposition. In a second step (Section 5.2), we will then show how the algorithm can be implemented such that its runtime is O(log^{∗ }n). For the slow version of the algorithm, we assume that all nodes know the minimum dis- tance d_{min }between any two nodes. This assumption would not be necessary. However, making the assumption results in a simpler, easier to understand algorithm. For the fast im- plementation, the assumption is not needed anymore. The computing of the decomposition is described by Algorithm 1.

Algorithm 1 starts with a small radius r which is increased by a factor 2 in every iteration of the while loop. At the beginning, the set V of possible cluster leaders contains all nodes. In each iteration, a subset of the nodes is selected such that the nodes selected in the subset form a maximal independent set on the graph of all edges of length ≤ r.

Lemma 5.1. Algorithm 1 computes a (2, 2^{4ρ})-decomposi- tion where ρ is the doubling dimension of the underlying metric. The maximum degree of the cluster graph is at most

2^{4ρ }

1.

## Algorithm 1 Network Decomposition: Clustering

1: r := min{2 |λ ∈ 2: V := V ;

∧ 2 ≥ d_{min }

};

3: while r ≤ 1/2 do

4: 5: 6: 7:

G := (V, E) with E = {{u, v}|d(u, v) < r}; compute MIS on G; V := {v ∈ V|v in MIS}; r := r · 2

[9, 20]

8: od; 9: All nodes in V are cluster leaders, the other nodes belong

to the cluster of the nearest leader.

10:

## Let

### C

be

the

maximum

degree

of

the

cluster

graph

## G_{C }. Color G_{C }with

### C

+

1 colors.

[9, 20]

Proof We first prove that each node has a cluster leader at distance at most 1 and that therefore, the diameter of each cluster is at most 2. The algorithm maintains a set V of nodes which are candidates for becoming cluster leader. In each iteration, some nodes are removed from V. We have to prove that for all nodes u which are removed, there is a node v with d(u, v) ≤ 1 which stays in V until the end,

that is, v becomes cluster leader. Let r_{u }= 2 be the radius at which u is removed from V.

u

(λ_{u }

∈

)

Whenever

a node is removed from V, there is a node at distance at most r which stays in V. Otherwise, the independent set which is computed in line 5 is not maximal. Hence, after removing u, there is a node u_{0 }∈ V with d(u, u_{0}) ≤ r_{u}. If u is removed in the subsequent iteration, there is a node u with d(u_{0}, u_{1}) ≤ 2r_{u }which remains in V. We hence get a sequence u_{0}, u_{1}, . . . , u_{i}, . . . of nodes where d(u_{i }_{1}, u_{i}) ≤ 2^{i}r_{u }such that u_{i }remains in V, i iterations after the removal of u. Summing up the distances results in a geometric series. For the distance between u and u_{i}, we therefore get 0 1

i

d(u, u_{i}) ≤

## X

2^{j }r_{u }

< 2^{i+1 }

r_{u }

= 2r_{u },

j=0

where r_{u }is the radius of the iteration where node u_{i }remains in V and where u_{i 1 }is removed from V. Let v be the last node in the sequence, that is, v is a cluster leader. Because the radius of the last iteration of Algorithm 1 is 1/2, we have d(u, v) < 1. Thus, the radius of each cluster is at most 1.

## It now remains to show that the maximum degree

### C

of

the cluster graph is at most 2^{4ρ }

1. On the one hand, from

the last iteration of the algorithm (r = 1/2), it is guaranteed that the distance between any two cluster leaders is more than 1/2. Otherwise, the nodes of the MIS of line 5 would not be independent. Therefore, each ball of radius 1/4 or smaller contains at most one cluster leader. On the other hand, because the radius of each cluster is at most 1, the distance between two cluster leaders of adjacent clusters is at most 3. This means that for a cluster leader v, all leaders of

a d j a c e n t c l u s t e r s a r e i n B 3

(v), the ball with radius 3 around

v. 2^{4ρ }

B y t h e d e fi n i t i o n o f ρ , B 3 ( v ) c a n b e c o v e r e d b y a t m o s t balls of radius 3/16 < 1/4. Including v, the number of

c l u s t e r l e a d e r s i n B 3 ( v ) i s t h e r e f o r e a t m o s t 2 4 ρ .

We will now have a close look at the complexity of a single iteration of the while loop of Algorithm 1. From a complex- ity point of view, the most important part is the computa- tion of the MIS in line 5. Everything else (computing the neighbors in G and informing neighbors about new V) can