# Independent Set

For an undirected graph $G = (V,E)$, an independent set $S \sub V$ satisfies $\forall u,v \in S, uv\notin E$

## Independent set is NP complete

For an input $G$, solution $S$, we need to show that S can be verified quickly, but cannot be found in poly time.

Checking if $S$ is a solution is poly time. For each pair $x, y\in S$, check if $xy \in E$. This is worst case $O(E^2)$

Now we will reduce 3SAT to Independent Set.