## 4 Independent Set
### Algorithm for Unit Disk Graphs  
We present our local approximation algorithm for independent set in unit disk graphs. Let \(G=(V,E)\) be a unit disk graph. The main idea of the algorithm is that since the vertices in one hexagon form a clique at most one vertex per hexagon can be in an independent set. The algorithm works as follows: InFigure 11: Several tiles arranged together. Figure 10: Resolving ambiguities at the border of hexagons. Figure 9: One tile consisting of 7 hexagons. each hexagon \(h\) we define the vertex which is closest to the center to be the head vertex \(v_{h}\) (ambiguities are resolved by choosing the vertex with the smallest \(x\)-coordinate among the vertices with the same distance to the center and if this is ambiguous we choose the vertex with the smallest \(y\)-coordinate). If \(v_{h}\) is _not_ adjacent to a vertex in a hexagon with a lower class number we assign \(v_{h}\) to the independent set \(I\). ```
1// Algorithm is executed independently by each node \(v\);
2 Find all vertices in \(N(v)\);
3 Determine the hexagon \(h\) of \(v\) and \(class(h)\);
4 if\(v\) is the head vertex of \(h\)then
5 if\(v\) is NOT adjacent to a vertex in a hexagon \(h^{\prime}\) with \(class(h^{\prime})<class(h)\)then
6 Assign \(v\) to the independent set \(I\);
7
8 end if
9
10 end for
```  
**Algorithm 5**Local algorithm for finding an independent set in a unit disk graph  
We prove the correctness of Algorithm 5, its approximation factor, its locality and its processing time in Theorem 8. **Theorem 8**. : _Let \(G\) be a unit disk graph. Algorithm 5 has the following properties:_  
1. _The computed set_ \(I\) _is an independent set for_ \(G\)_._
2. _Let_ \(I_{OPT}\) _be an optimal independent set. It holds that_ \(|I|\geq\frac{1}{1801}\cdot|I_{OPT}|\)_._
3. _Whether or not a vertex_ \(v\) _is in_ \(I\) _depends only on the vertices at most one hop away from_ \(v\)_, i.e. Algorithm_ 5 _is local._
4. _The processing time for a vertex_ \(v\) _is linear in the number of vertices adjacent to_ \(v\)_._  
Proof. : First we want to show that \(I\) is indeed an independent set for \(G\). Assume on the contrary that there are two adjacent vertices \(v\in I\) and \(v^{\prime}\in I\). Since at most one vertex per hexagon is assigned to \(I\) it follows that \(v\) and \(v^{\prime}\) are in different hexagons \(h\) and \(h^{\prime}\) respectively. From Proposition 1 it follows that \(class(h)\
eq class(h^{\prime})\), so without loss of generality we can assume that \(class(h)>class(h^{\prime})\). But from the construction it follows that a vertex \(v\) in a hexagon \(h\) is not assigned to \(I\) if it is adjacent to a vertex \(v^{\prime}\) in a hexagon \(h^{\prime}\) with \(class(h)>class(h^{\prime})\). This is a contradiction. So the set \(I\) is an independent set for \(G\). Now we want to prove the approximation ratio of Algorithm 5. Let \(I_{OPT}\) be an optimal independent set for \(G\). Denote by \(H\) the set of hexagons which contain vertices from \(G\). Since the vertices in a hexagon form a clique, at most one vertex per hexagon can be part of an independent set. So \(|H|\) is an upper bound for \(|I_{OPT}|\). For a hexagon \(h\) we denote by \(B(h)\) the union of \(h\) and all hexagons \(h^{\prime}\) such that \(class(h)<class(h^{\prime})\) and \(h^{\prime}\) contains a vertex which is adjacent to a vertex in \(h\). For a set of hexagons \(H^{\prime}\) we define \(B(H^{\prime}):=\bigcup_{h^{\prime}\in H^{\prime}}B(h^{\prime})\). We define recursively \(B^{0}(h):=\{h\}\) and \(B^{i}(h):=B(B^{i-1}(h))\)As there are only seven different classes of hexagons, it follows that \(B^{7-i}(h)=B^{7-i+k}(h)\) for hexagons of class \(i\) and for all \(k\geq 0\). We define \(\tilde{B}(h):=B^{7-class(h)}(h)\). Intuitively we can say that the hexagon \(h\) blocks all hexagons in \(\tilde{B}(h)\). Consider a graph \(G^{\prime}=(V^{\prime},E^{\prime})\) with one vertex per hexagon in \(H\) and with an edge between two vertices if and only if their respective hexagons are adjacent.