This slideshow presents how to reduce a 3-SAT problem instance to an equivalent CLIQUE problem instance in polynomial time.

Given a boolean formula in 3 CNF, the 3-SAT problem is to find whether the formula is satisfiable.

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$.

A formula $\Phi$ of $k$ three-literal clauses can be reduced to a $k$-Clique problem in the following way:

Construct a graph G of $k$ clusters with a maximum of $3$ nodes in each cluster.

Each cluster corresponds to a clause in $\Phi$.

Each node in a cluster is labeled with a literal from the clause.


An edge is put between all pairs of nodes in different clusters except for pairs of the form $(x, \overline{x}$)


No edge is put between any pair of nodes in the same cluster.

Construction of cluster of nodes corresponding to clauses in 3 CNF

$\Phi =$

$(x_2 + x_1 + \overline{x_3})$

.

$(\overline{x_1} + \overline{x_2} + x_4)$

$\cdot$

$(x_2 + \overline{x_4} + x_3)$

Connecting the nodes in the graph

1. If two nodes in the graph are connected, the corresponding literals can simultaneously be assigned $True$.
(This is true since there is no edge between nodes corresponding to literals of type $x$ and $\overline{x}$.)


2. If two literals not from the same clause can be assigned $True$ simultaneously, the nodes corresponding to these literals in the graph are connected.


3. Construction of the graph can be performed in polynomial time

$G$ has a $k$-clique if and only if $\Phi$ is satisfiable.

1. If the graph $G$ has a $k$-clique, the clique has exacty one node from each cluster.
(This is because no two nodes from the same cluster are connected to each other, hence they can never be a part of the same clique.)
All nodes in a clique are connected, hence all corresponding literals can be assigned $True$ simultaneously.
Each literal belongs to exactly one of the $k$-clauses. Hence $\Phi$ is satisfiable.

2. If $\Phi$ is satisfiable, let A be a satisfying assignment. Select from each clause a literal that is $True$ in A to construct a set S. $||S|| = k$.Since no two literals in S are from the same clause and all of them are simultaneously $True$, all the corresponding nodes in the graph are connected to each other, forming a k-clique. Hence, the graph has a $k$-clique.

The corresponding assignment: $x_2 = True , x_3 = True , x_4 = True$.

$\Phi$ is $True$ for the corresponding assignment: $x_2 = True , x_3= True , x_4 = True$.