## 4 Independent Set
### Algorithm for Unit Line Graphs  
We present a local algorithm for independent set with locality one on unit line graphs (ULGs). For the set \(I\) computed by this algorithm it holds that \(|I|\geq\left\lfloor\frac{1}{2}\cdot|I_{OPT}|\right\rfloor\) and \(|I|\geq 1\) (with \(I_{OPT}\) being an optimal independent set). Like in Algorithm 2 we divide the line into units of width one. Now we present the algorithm in detail. Let \(G=(V,E)\) be a unit line graph. For a vertex \(v\) we denote by \(v_{x}\) its \(x\)-coordinate. For all integers \(i\) we define \(V_{i}:=\{v\in V|i\leq v_{x}<i+1\}\). We define \(H:=\{i|V_{i}\
eq\emptyset\}\). For all \(i\in H\) we define \(v[i]\) to be the vertex with the smallest \(x\)-coordinate in \(V_{i}\). Now we partition the vertices \(v[i]\) into two sets \(V_{1}\) and \(V_{2}\). Let \(V_{1}:=\{v[i]|i\in H\wedge i\text{ is odd}\}\) and \(V_{2}:=\{v[i]|i\in H\wedge i\text{ is even}\}\). Denote by \(V_{2}^{\prime}\subseteq V_{2}\) the subset of \(V_{2}\) consisting of the vertices \(v[i]\) which are not adjacent to vertices \(v^{\prime}\) with \(v^{\prime}\in V_{i-1}\) or \(v^{\prime}\in V_{i+1}\) (so for such a vertex \(v^{\prime}\) it would hold that \(v_{x}^{\prime}<i\) or \(v_{x}^{\prime}\geq 1\)). We define the independent set \(I\) as \(I:=V_{1}\cup V_{2}^{\prime}\). The output is the set \(I\). We refer to this as Algorithm 6. We prove the correctness of Algorithm 6, its approximation factor, its locality and its processing time in Theorem 10. **Theorem 10**. : _Let \(G\) be a unit line graph. Algorithm 6 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\left\lfloor\frac{1}{2}\cdot|I_{OPT}|\right\rfloor\) _and_ \(|I|\geq 1\)_._
3. _Whether or not a vertex_ \(v\) _is in_ \(I\) _depends only on the vertices which are at most_ \(k\) _hops away from_ \(v\)_, i.e. Algorithm_ 6 _is local._
4. _The processing time for a vertex_ \(v\) _is linear in the number of vertices adjacent to_ \(v\)_._  
Proof. : It holds that the Euclidean distance between two vertices in \(V_{1}\) is strictly greater than one. So \(V_{1}\) is an independent set. Since all vertices in \(V_{2}^{\prime}\) are not adjacent to vertices \(v^{\prime}\) with \(v^{\prime}_{x}<i\) or \(v^{\prime}_{x}\geq i+1\) it holds that a vertex in \(V_{2}^{\prime}\) cannot be adjacent to a vertex in \(V_{1}\). Like for \(V_{1}\) it holds that the Euclidean distance between two vertices in \(V_{2}\) is strictly greater than one. So no two vertices in \(V_{2}^{\prime}\) are adjacent. All this implies that \(I=V_{1}\cup V_{2}^{\prime}\) is in independent set. Now we want to prove the approximation ratio of Algorithm 6. Let \(i\) be an integer. The vertices in \(V_{i}\) form a clique. Therefore at most one vertex in \(V_{i}\) can be in \(I\). So \(|H|\) is an upper bound for \(|I_{OPT}|\). If \(|H|\) is even then \(|V_{1}|=\frac{|H|}{2}\). If \(|H|\) is odd then either \(|V_{1}|=\frac{|H|+1}{2}\) or \(|V_{1}|=\frac{|H|-1}{2}\). So in either case it holds that \(|I|\geq|V_{1}|\geq\left\lfloor\frac{1}{2}\cdot|I_{OPT}|\right\rfloor\). If \(|V_{1}|\geq 1\) it clearly holds that \(|I|\geq 1\). If \(|V_{1}|=0\) there must be one set \(V_{i}\) with \(V_{i}\
eq\emptyset\) and \(i\) being even (since otherwise the graph would be empty and for the empty graph the theorem is trivially true). It also holds that \(V_{i-1}=\emptyset\) and \(V_{i+1}=\emptyset\). So \(v[i]\) is not adjacent to any vertices in \(V_{i-1}\) or \(V_{i+1}\) and therefore \(v[i]\in I\). This implies that \(|I|\geq 1\). Let \(v\in V_{i}\) be a vertex. In order to determine whether \(v\in I\) we need to explore the vertices in \(V_{i}\) and we need to determine whether \(v\) is adjacent to a vertex \(v^{\prime}\) with \(v^{\prime}\in V_{i-1}\) or \(v^{\prime}\in V_{i+1}\). All this requires only the knowledge of the vertices in \(N(v)\). So the locality distance of Algorithm 6 is one.