## 3 Connected Dominating Set
### Algorithm for Unit Disk Graphs  
We present our approximation algorithm for connected dominating set in unit disk graphs with locality two. Let \(G=(V,E)\) be a connected unit disk graph. We use the same tiling of the plane as introduced in Section 2. The algorithm works as follows: Consider one hexagon \(h\). We consider each hexagon \(h^{\prime}\) such that there are pairs of adjacent vertices \(v\) and \(v^{\prime}\) with \(v\in h\), \(v^{\prime}\in h^{\prime}\). We compute the two adjacent vertices \(v\in h\), \(v^{\prime}\in h^{\prime}\) which are closest to each other (ties are resolved by some resolving method, e.g., by choosing the pair where the vertex in \(h\) has the smallest \(x\)-coordinate etc.). We assign \(v\) and \(v^{\prime}\) to the connected dominating set \(CD\). Do this for all hexagons \(h^{\prime}\) with the above property. If there are no such hexagons \(h^{\prime}\) we assign the vertex \(v\in h\) to \(CD\) which is closest to the center of \(h\) (ties are broken like in Algorithm 1). The above description is presented in Algorithm 3. We prove the correctness and the other properties of Algorithm 3 in Theorem 4. **Theorem 4**. : _Let \(G\) be a unit disk graph. Algorithm 3 has the following properties:_  
1. _The computed set_ \(CD\) _is a connected dominating set for_ \(G\)_._
2. _Let_ \(CD_{OPT}\) _be an optimal connected dominating set. It holds that_ \(|CD|\leq 216\cdot|CD_{OPT}|\)_._
3. _Whether or not a vertex_ \(v\) _is in_ \(CD\) _depends only on the vertices at most two hops away from_ \(v\)_, i.e. Algorithm_ 3 _is local._
4. _The processing time for a vertex_ \(v\) _is quadratic in the number of vertices adjacent to_ \(v\)_._  
Proof. : First we prove that the set \(CD\) is indeed a connected dominating set for \(G\). From the construction it follows that in each hexagon which contains vertices of \(G\) at least one vertex is assigned to \(CD\). So\(CD\) is a dominating set for \(G\). If in \(G\) a vertex \(\bar{v}\) in a hexagon \(h\) is adjacent to a vertex \(\bar{v}^{\prime}\) in a hexagon \(h^{\prime}\), then the algorithm ensures that for two adjacent vertices \(v\) and \(v^{\prime}\) with \(v\in h\) and \(v^{\prime}\in h^{\prime}\) it holds that \(v\in CD\) and \(v^{\prime}\in CD\). So in \(G\) there is an edge between two vertices in two different hexagons if and only if in \(G\) restricted to \(CD\) there is an edge between these hexagons. It follows that \(CD\) is connected since \(G\) is connected. Now we want to prove the approximation ratio of Algorithm 3. In Algorithm 1 at most one vertex per hexagon is assigned to the connected dominating set. We showed in Theorem 1 that this ensures an approximation ratio of \(12\) in comparison with an optimal dominating set. Now for one hexagon \(h\) there are at most \(18\) hexagons \(h^{\prime}\) such that there are edges between vertices in \(h\) and \(h^{\prime}\). So at most \(18\) vertices from \(h\) are assigned to \(CD\). Let \(D_{OPT}\) be an optimal dominating set, let \(CD_{OPT}\) be an optimal connected dominating set and let \(D\) be the dominating set computed by Algorithm 1. It follows that  
\[|CD| \leq 18\cdot|D|\] \[\leq 18\cdot 12\cdot|D_{OPT}|\] \[\leq 18\cdot 12\cdot|CD_{OPT}|\] \[= 216\cdot|CD_{OPT}|\]  
Now we prove the locality of Algorithm 3. Consider a vertex \(v\) in a hexagon \(h\). In order to find out whether or not \(v\) is assigned to \(CD\) we need to find out whether \(v\) is adjacent to a vertex \(v^{\prime}\) in a hexagon \(h^{\prime}\) with \(h\
eq h^{\prime}\) and what other vertices \(\bar{v}\in h\) are adjacent to vertices \(\bar{v}^{\prime}\in h^{\prime}\). In order to do this, we need to explore all vertices which are at most two hops away from \(v\). To check whether there are generally vertices in \(h\) which are adjacent to vertices in other hexagons (if not, the vertex closest to the center of \(h\) is assigned to \(CD\)), we need to explore the vertices which are at most two hops away from \(v\). Finally we prove the processing time of Algorithm 3.