CLIQUE, INDEPENDENT SET, and VERTEX COVER are polynomially interreducible

For any subset $S\subseteq V$, [L1] implies that the vertices of $S$ are pairwise adjacent in $G$ if and only if they are pairwise nonadjacent in $\bar{G}$. Thus $S$ is a clique in $G$ if and only if it is an independent set in $\bar{G}$. Therefore $(G,k)\mapsto (\bar{G},k)$ is a polynomial-time many-one reduction from CLIQUE to INDEPENDENT SET, and the same map is also a reduction in the reverse direction.

For any subset $I\subseteq V$, the complement $V\setminus I$ is a vertex cover if and only if $I$ is an independent set. Indeed, if $I$ is independent, every edge has at least one endpoint outside $I$, so it is covered by $V\setminus I$. Conversely, if $V\setminus I$ is a vertex cover and two vertices of $I$ were adjacent, that edge would have no endpoint in $V\setminus I$, a contradiction. Hence, whenever $k\le \mathrm{\mid }V\mathrm{\mid }$, the graph $G$ has an independent set of size at least $k$ if and only if it has a vertex cover of size at most $\mathrm{\mid }V\mathrm{\mid }-k$.

Use step 1.2 to define total reductions. For INDEPENDENT SET to VERTEX COVER, map $(G,k)$ to $(G,\mathrm{\mid }V\mathrm{\mid }-k)$ when $k\le \mathrm{\mid }V\mathrm{\mid }$, and map it to the fixed no-instance $(K_2,0)$ when $k>\mathrm{\mid }V\mathrm{\mid }$. For VERTEX COVER to INDEPENDENT SET, map $(G,k)$ to $(G,\mathrm{\mid }V\mathrm{\mid }-k)$ when $k\le \mathrm{\mid }V\mathrm{\mid }$, and map it to the fixed yes-instance $(K_1,1)$ when $k>\mathrm{\mid }V\mathrm{\mid }$. The exceptional branches are correct because no graph has an independent set larger than its vertex set, while every graph has a vertex cover of size at most $\mathrm{\mid }V\mathrm{\mid }$. Both maps are clearly polynomial-time.

Step 1.1 gives reductions between CLIQUE and INDEPENDENT SET, and step 2.1 gives reductions between INDEPENDENT SET and VERTEX COVER. Composing these reductions yields reductions in every direction among the three problems.