This slideshow presents how to reducean input instance to CLIQUE to an equivalent input instance to INDEPENDENT SET in polynomial time

For a given graph $G = ( V , E )$ and integer $k$, the CLIQUE problem is to find whether $G$ contains a clique of size $\geq k$.

For a given graph $G' = (V' , E')$ and integer $k'$, the INDEPENDENT SET problem is to find whether $G'$ contains an Independent Set of size $\geq k'$.

To reduce a CLIQUE input instance to an INDEPENDENT SET input instance for a given graph $G = (V , E)$, construct a complementary graph $G' = (V' , E')$ such that

1. $V = V'$ , that is the complement graph will have the same vertices as the original graph.

2. $E'$ is the complement of $E$ that is $G'$ has all the edges that is not present in $G$.

Construction of the complementary graph can be done in polynomial time.

1. If there is an independent set of size $k$ in the complement graph $G'$, it implies no two vertices
share an edge in $G'$, which further implies all of those vertices share an edge with all others in $G$ forming
a clique. That is, there exists a clique of size $k$ in $G$.

2. If there is a clique of size $k$ in the graph $G$, it implies all vertices share an edge with all others in $G$,
which further implies no two of these vertices share an edge in $G'$ (thus forming an Independent Set. That is,
there exists an independent set of size $k$ in $G'$.