Problem $4(k-$Clique Problem, $35$ points$)$

The relevant material for this problem will be covered in the Mon $4/29$ lecture.

For a given undirected graph $G=(V,E),$ a clique is defined as a subset of vertices

SsubeV where there is an edge between any pair of distinct vertices in $S,$ i$.$e$.$ AAu,vinS and

$uv,\{u,v\}inE.$ In the $k-$clique problem, we are given as input an undirected graph $G$ and

a positive integer $k,$ and need to output whether there exists a clique of $k$ vertices in $G.$ We

will show that this problem is NP$-$complete.

$($a$)$ Show that the $k-$clique problem is in NP$.$ Here, you can either directly show that you can

verify the witness to a $k-$clique instance in polynomial time, or you can show that you can

efficiently reduce $k-$clique to some NP problem we have talked about $(3-$SAT$/$IS$/$VC$).$

$($b$)$ Show that the $k-$clique problem is NP$-$hard. Here, you should efficiently reduce one of

the NP$-$complete problems $(3-$SAT$/$IS$/$VC$)$ to a $k-$clique problem, i$.$e$.$ show how you can

use a solver for a $k-$clique problem to efficiently $($within polynomial time overhead$)$ solve

a $3-$SAT$/$IS$/$VC problem.