## 2 Dominating Set
### Lower Bound  
Here we present a construction which enables us to give a lower bound for the approximation factor of a local algorithm for dominating set with a locality distance of \(k\). **Theorem 2**. : _Let \(\mathcal{A}\) be a local algorithm for dominating set in unit line graphs with locality distance \(k\) in the setting of location aware nodes. The best performance ratio which can be achieved by \(\mathcal{A}\) is_  
* \(1+\frac{3}{2k+3}\) _if_ \(k\equiv 0\) _mod_ \(3\)__
* \(1+\frac{3}{2k+1}\) _if_ \(k\equiv 1\) _mod_ \(3\)__
* \(1+\frac{3}{2k+2}\) _if_ \(k\equiv 2\) _mod_ \(3\)__  
Figure 3: A vertex in the gray area excluding the center of \(h\) can only be adjacent to vertices in these 12 hexagons. _Algorithms_**2008**, \(1\)  
Figure 4: Tight example for Algorithm 1. To make the figure clearer the edges which are not adjacent to \(v\) are omitted. Figure 5: The enlargement of our construction of the tight example. It is possible to extend this to an arbitrarily large graph. _i.e., for arbitrary \(k\) the best performance ratio is \(1+\frac{3}{2k+\left(\left(k-1\right)\text{mod }3\right)+1}\)._  
Proof. : Consider the unit line graph \(G=(V,E)\) consisting of \(4+2k\) vertices (see Figure 6). Denote by \(V_{M}\) the four vertices in the middle. Let \(D\) be the dominating set which is computed by \(\mathcal{A}\) for \(G\). We distinguish three cases:  
* \(k\equiv 0\text{ mod }3\). Then there must be at least one vertex \(u\in V_{M}\) such that \(u\in D\) (otherwise \(D\) would not be a dominating set). Consider the graph \(G_{0}\) consisting of \(u\) and \(k\) vertices on the left and \(k+2\) vertices on the right of \(u\) (see Figure 6). Let \(D_{0}\) be the dominating set which is computed by \(\mathcal{A}\) for \(G_{0}\). An optimal dominating set for \(G_{0}\) has \(\frac{2k+3}{3}\) vertices. However, as \(u\in D\) and the locality of \(\mathcal{A}\) is \(k\) it follows that \(u\in D_{0}\). Therefore it follows that \(|D_{0}|\geq\left\lceil\frac{k-1}{3}\right\rceil+1+\left\lceil\frac{k+1}{3} \right\rceil=\frac{2k+6}{3}\). So the approximation ratio of \(\mathcal{A}\) is a least \(\frac{2k+6}{3}/\frac{2k+3}{3}=\frac{2k+6}{2k+3}=1+\frac{3}{2k+3}\). * \(k\equiv 1\text{ mod }3\). We distinguish whether or not there are vertices in \(V_{M}\) which are not in \(D\). If all vertices in \(V_{M}\) are in \(D\) then it holds that \(|D|\geq\left\lceil\frac{k-1}{3}\right\rceil+4+\left\lceil\frac{k-1}{3}\right\rceil =\frac{2k+10}{3}\). However, an optimal dominating set for \(G\) has at most \(\frac{2k+4}{3}\) vertices. So then the approximation ratio of \(\mathcal{A}\) is at least \(\frac{2k+10}{3}/\frac{2k+4}{3}=\frac{2k+10}{2k+4}=1+\frac{6}{2k+3}\). If there is a vertex \(v\in V_{M}\) with \(v\
otin D\) then we consider the graph \(G_{1}\) which consists of \(v\) and \(k\) vertices on the left and on the right of \(v\) (see Figure 6). Let \(D_{1}\) be the dominating set which is computed by \(\mathcal{A}\) for \(G_{1}\). An optimal dominating set for \(G_{1}\) has \(\frac{2k+1}{3}\) vertices. However, as \(v\
otin D\) and the locality of \(\mathcal{A}\) is \(k\) it follows that \(v\
otin D_{1}\). This implies that \(|D_{1}|\geq\left\lceil\frac{k-1}{3}\right\rceil+2+\left\lceil\frac{k-1}{3} \right\rceil=\frac{2k+4}{3}\). So the approximation ratio of \(\mathcal{A}\) is a least \(\frac{2k+4}{3}/\frac{2k+1}{3}=\frac{2k+4}{2k+1}=1+\frac{3}{2k+1}\). As \(1+\frac{3}{2k+1}\leq 1+\frac{6}{2k+3}\) it follows that if \(k\equiv 1\text{ mod }3\) then the approximation ratio of \(\mathcal{A}\) is a least \(1+\frac{3}{2k+1}\). * \(k\equiv 2\text{ mod }3\). Then there must be at least one vertex \(u\in V_{M}\) such that \(u\in D\) (otherwise \(D\) would not be a dominating set). Consider the graph \(G_{2}\) consisting of \(u\) and \(k\) vertices on the left and \(k+1\) vertices on the right of \(u\) (see Figure 6). Let \(D_{2}\) be the dominating set which is computed by \(\mathcal{A}\) for \(G_{2}\). An optimal dominating set for \(G_{2}\) has \(\frac{2k+2}{3}\) vertices.