## 3 Connected Dominating Set
### No Constant Ratio Approximation Algorithm with Locality One  
We prove that there is no local algorithm for connected dominating set with locality one which achieves a constant approximation ratio.  
**Theorem 5**.: _Let \(\mathcal{A}\) be a local algorithm with locality one for connected dominating set in the setting of location aware nodes. For every constant \(c\) there is a graph \(G_{c}\) such that \(\mathcal{A}\) achieves an approximation ratio worse than \(c\) when computing a connected dominating set for \(G_{c}\)._  
Proof.: Without loss of generality we assume that \(c\) is an integer. Consider two circles of diameters one and three which are placed inside of each other (see Figure 7). Consider the unit disk graph \(G_{c}\) defined as follows: There are \(21\cdot c\) vertices distributed on the inner ring. Denote these vertices by \(V_{I}\). On the outer ring there are another \(21\cdot c\) vertices such that each of them is opposite to one vertex in \(V_{I}\). We denote by \(V_{O}\) the vertices on the outer ring. Since \(G_{c}\) is a unit disk graph an edge between two vertices exists if and only if the Euclidean distance between the vertices is at most one. For each vertex \(v\in V_{O}\) we define the unit disk graph \(G_{v}\) as follows: it consists of the vertices \(V_{I}\) and the vertex \(v\). Denote by \(v^{\prime}\) the vertex opposite of \(v\) on the inner ring. Again, an edge between two vertices exists if and only if the Euclidean distance between two vertices is at most one. Figure 7 shows this construction for \(c=1\). When \(\mathcal{A}\) computes a connected dominating set \(CD_{v}\) for \(G_{v}\) it holds that \(v^{\prime}\in CD_{v}\) (since \(v\) must be dominated either by \(v^{\prime}\) or by \(v\) itself which implies for \(CD_{v}\) to be connected that \(v^{\prime}\) must be in \(CD_{v}\) as well). When \(\mathcal{A}\) computes a connected dominating set \(CD\) for \(G_{c}\) it must take the same decision about assigning \(v^{\prime}\) to \(CD\) as in \(G_{v}\) (since the locality of \(\mathcal{A}\) is one). So \(v^{\prime}\in CD\). With the same argument we can show that for every vertex \(u\in V_{I}\) it holds that \(u\in CD\). So \(V_{I}\subseteq CD\) and therefore \(|CD|\geq 21\cdot c\). But since the length of the outer ring is \(3\pi\) it holds that the size of a maximal independent set is at most \(\lfloor 3\pi\rfloor=10\) and therefore the size of a connected dominating set for \(G_{c}\) is at most \(20\) (we can construct this by taking a maximal independent subset \(I_{O}\) of \(V_{O}\) and add all vertices in \(V_{I}\) which are opposite of vertices in \(I_{O}\)). Denote by \(CD_{OPT}\) an optimal dominating set for \(G_{c}\). So for the approximation ratio \(|CD|/\left|CD_{OPT}\right|\) it holds that  
\[\frac{|CD|}{|CD_{OPT}|}\geq\frac{21\cdot c}{20}>c\]  
**Figure 7**. The graph \(G_{c}\) for \(c=1\) and the graph \(G_{v}\) for the vertex \(v\). In order to make the figures clearer we omit the edges of the graphs.  
**Corollary 2**.: _Let \(\mathcal{A}\) be a local algorithm with locality one for connected dominating set in the setting of location aware nodes. The approximation ratio of \(\mathcal{A}\) is bounded from below by \(n/40\), i.e., it is in \(\Theta(n)\)._  
Proof.: We apply the construction in the proof of Theorem 5 to obtain the family of graphs \(G_{c}\). For each graph \(G_{c}\) the following holds: Let \(CD\) be the connected dominating set for \(G_{c}\) which is computed by \(\mathcal{A}\). All vertices in the inner ring are assigned to \(CD\) by \(\mathcal{A}\) (see the proof of Theorem 5). As half of the vertices of \(G_{c}\) are on the inner ring, it holds that \(|CD|\geq n/2\). However, an optimal connected dominating set \(CD_{OPT}\) for \(G_{c}\) has at most \(20\) vertices, so \(|CD_{OPT}|\leq 20\). So for the approximation ratio \(|CD|\,/\,|CD_{OPT}|\) it holds that  
\[\frac{|CD|}{|CD_{OPT}|}\geq\frac{n}{2}\cdot\frac{1}{20}=\frac{n}{40}\]