Given $G = \left( {V,E} \right)$ and $k$, does there exist $U \subseteq V$ with $|U| \geq k$ such that $\left\{ {u,v} \right\} \in E$ for all distinct vertices $u,v \in U$?

$\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{has a clique of size}\ k} \right\}$

• No specification on size: in our example above, there are cliques of size 0 through 3

Theorem.

CLIQUE is NP-complete: i.e. CLIQUE is NP-hard, and CLIQUE is in NP.

Proof.

CLIQUE is in NP: because there exists a verifier that can check a possible clique in polytime.

CLIQUE is NP-hard: because 3SAT (known NP-hard problem) reduces to CLIQUE. How can we do that?

Proof. $\text{3SAT}\underset{P}{\leq}\text{CLIQUE}$ (reduction)

$x \in \text{3SAT}$ maps to $f(x) \in \text{CLIQUE}$

• If $x = \left\langle \varphi \right\rangle$ where $\varphi$ is a satisfiable 3CNF formula, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has a clique of size $k$.

$x \notin \text{3SAT}$ maps to $f(x) \notin \text{CLIQUE}$

• If $x = \left\langle \varphi \right\rangle$ where $\varphi$ has no satisfiable assignments, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has no clique of size $k$.
• junk can map to junk

We can show 3SAT can be solved by finding a clique of size $k$.

• Connect every vertex in a block to every other vertex that is not its inverse.
• Then, every clique of size $k$ is a possible satisfiable assignment.
• We can’t have $x_{i}$ and $x_{i}^{\_}$ both being true: which is represented by no connecting edges.

We still need to “decode” $f(x) \in B$ to $x \in A$… i.e. $f(x) \in \text{CLIQUE}\Rightarrow x \in \text{3SAT}$.

• Let $U$ be a clique of size $k$. We must divy it up so that there is exactly one vertex in each group.
• Given a $f(x) \in \text{CLIQUE}$ constructed from a $\text{3SAT}$ problem, then we find a satisfying $x \in \text{3SAT}$.

Aside: suppose we want to ensure there is a clique of at least size $k - 1$. We can make a separate, disconnected clique of $k - 1$ vertices. What’s this useful for? Don’t know yet…