4. Clique Problem

Clique Problem (CLIQUE)

The Clique Problem (CLIQUE) takes an input of:

• an undirected graph $G=(V,E)$
• an integer $k>2$

It provides an output of $\top$ if and only if $G$ contains a clique of size $k$.

Clique

A clique is a subset of an undirected graph such that every two distinct vertices in the clique are adjacent.

Link to original

Link to original

Theorem: The Clique Problem belongs to NP

Input: An undirected graph $G=(V,E)$ and integer $k>2$.

1. We can decide whether $G$ contains a clique of size $k$ by checking every subset of vertices of size $k$. However, there are $\left(\begin{array}{c}n\\ k\end{array}\right)$ possible subsets which is not polynomial.
2. But, we can use an NDTM to check each subset in parallel, and as each subset requires us to check only $k^2$ edges, this is polynomial!

Theorem: The SAT problem is polynomially reducible to the Clique finding problem, $\text{SAT}{\le }_p\text{CLIQUE}$.

Input: Formula $F$ in CNF.

1. Construct a graph $G_F=(V,E)$ and choose an integer $k>2$ such that: $F$ is satisfiable $\iff$ $G_F$ has a clique of size $k$
2. Define $G_F=(V,E)$ from some given $F$. For example, given $F=(P\vee \neg Q\vee R)\wedge (\neg P\vee \neg Q\vee \neg R)\wedge (P\vee Q\vee \neg R)$:

• We convert each clause into their distinct vertices.
• Next, we connect all vertices together that are not in the same clause and do not conflict. Edges which conflict are highlighted in $\text{red}$ below. Formally $(L_1^i,L_2^j)\in E⟺i\ne j\text{ and }{L}_1\cancel{\equiv }\neg L_2$.
• Now we choose an appropriate integer $k$, which in this case is $k=\#\text{ clauses in }F$. In this example, $k=3$.
• We can make $F$ sastifiable when:

$P,Q$ are true $R$ is false	$P,Q,R$ are false	$R,P$ are true $Q$ is false

• Hence, we have that $F$ is satisfiable $⟺$ $G_F$ contains a clique of size $k$. Therefore $\text{SAT}{\le }_p\text{CLIQUE}$.

Theorem: CLIQUE is NP-complete

Since SAT is NP-hard, it follows that the Clique Problem must also be NP-hard. This gives us our lower-bound which proves CLIQUE is NP-complete.