## 3 Independent Set
### Time Complexity  
In this form the algorithm takes more than \(O(n^{2})\) time, because checking whether an induced subgraph is complete is slow. However, we can maintain a set of vertices, \(C\), which we have seen to induce a complete graph. We will create an efficient procedure to check if a subgraph is complete, and to return some additional information to be used for future calls if the subgraph is not complete. ```
\(C^{\prime}:=C\) for\(v\in U\setminus C\)do if\(C^{\prime}\setminus N^{+}(v)=\emptyset\)then \(C^{\prime}:=C^{\prime}\cup\{v\}\) else  let \(u\in C^{\prime}\setminus N^{+}(v)\) return\((uv,C^{\prime})\) endif endfor return\((False,C^{\prime})\). ```  
**Algorithm 3**\(\texttt{antiedge}(G,U,C)\)  
The following lemma summarises the behaviour of Algorithm 3. **Lemma 3.3**. : _Let \(C\subseteq U\) and suppose that \(G[C]\) is complete. If \(G[U]\) is complete, then \(\texttt{antiedge}(G,U,C)\) returns \((False,U)\); if not, then it returns \((uv,C^{\prime})\) such that_  
1. \(uv\in C^{\prime}\times(U\setminus C^{\prime})-E(G)\) _i.e._ \(u\in C^{\prime}\)_,_ \(v\in U\setminus C^{\prime}\)_,_ \(uv\
otin E(G)\)__2. \(C\subseteq C^{\prime}\subseteq U\)
3. \(G[C^{\prime}]\) _is complete_  
Proof. : Easy checking. ```
\(I:=\emptyset\); \(U:=V(G)\) \(e:=False\); \(C:=\emptyset\) \((e,C):=\texttt{antiedge}(G,U,C)\) while\(U\
eq\emptyset\)do if\(e=False\)then  pick an arbitrary \(u\in U\) return\(I\cup\{u\}\). else  Assume that \(e=u_{1}u_{2}\); \(u_{1},u_{2}\in U\) \(U_{1}:=(N^{+}(u_{1})\setminus N^{+}(u_{2}))\cap U\) \(U_{2}:=(N^{+}(u_{2})\setminus N^{+}(u_{1}))\cap U\) \((e_{1},C_{1}):=\texttt{antiedge}(G,U_{1},C\cap U_{1})\) \((e_{2},C_{2}):=\texttt{antiedge}(G,U_{2},C\cap U_{2})\) if\(e_{1}=False\)then if\(e_{2}=False\)then \(I:=I\cup\{u_{1},u_{2}\}\) \(U:=U\setminus(N^{+}(u_{1})\cup N^{+}(u_{2}))\) \((e,C):=\texttt{antiedge}(G,U,\emptyset)\) else \(I:=I\cup\{u_{1}\}\) \(U:=U\setminus N^{+}(u_{1})\) \(C:=C_{2};e:=e_{2}\) endif else if\(e_{2}=False\)then \(I:=I\cup\{u_{2}\}\) \(U:=U\setminus N^{+}(u_{2})\) \(C:=C_{1};e:=e_{1}\) else \(I:=I\cup\{u_{1},u_{2}\}\) \(U:=U\setminus(N^{+}(u_{1})\cup N^{+}(u_{2}))\) \((e,C):=\texttt{antiedge}(G,U,\emptyset)\) endif endif endif endwhile return\(I\)
```  
**Algorithm 4**\(\texttt{indep}(G)\)  
**Lemma 3.4**. : _Let \(U\) and \(C\) be the sets stored in the respective variables at the beginning of an iteration of the main loop of Algorithm 4, and let \(U^{\prime}\) and \(C^{\prime}\) be the sets stored at the beginning of the next iteration, if the algorithm does not terminate meanwhile. The following loop invariants hold:_  
1. \(G[C]\) _is complete and_ \(C\subseteq U\)_._
2. \(U^{\prime}\setminus C^{\prime}\subseteq U\setminus C\)_._  
A loop invariant is a condition which is true at the beginning of each iteration of a loop. **Proof. ** Observe that the initial values of \(U\) and \(C\), which are \(V\) and \(\emptyset\) respectively, guarantee by Lemma 3.3 that the values after the call to Algorithm 3 satisfy condition (1). Therefore, (1) holds for the first iteration. Concerning future iterations, observe that (1) guarantees the precondition of Lemma 3.3, which it turn guarantees (1) for the next iteration. We deduce that (1) does indeed give a loop invariant. By proving this we have proved that the preconditions of Lemma 3.3 are always met; and so we can use Lemma 3.3 throughout. If \(e=False\), then there is no next iteration, hence condition (2) is automatically correct. Now assume that \(e=u_{1}u_{2}\). Depending on \(e_{1}\) and \(e_{2}\) there are two cases for how many vertices are excluded. Case 1: one vertex is excluded. W.l.o.g. assume that \(u_{1}\) is excluded, so \(U^{\prime}=U\setminus N^{+}(u_{1})\), \(C\cap U_{2}\subseteq C^{\prime}\) and \(C\subseteq N^{+}(u_{1})\cup N^{+}(u_{2})\).