The following slideshow shows that an input instance to the 3-SAT
problem can be reduced to an equivalent input instance to the
CLIQUE problem in polynomial time.
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)$
$\overline{x_1}$
$\overline{x_2}$
$x_4$
$x_2$
$x_1$
$\overline{x_3}$
$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.
