How to Create a Graph Derived from the 3-CNF Formula

The Clique Problem

The clique problem is an optimization problem where we ask if a clique (complete subgraphs) of a given size $k$ exists in the graph.
The idea is to find the clique maximum size in a graph.

List of Facts

• A clique in a undirected graph $G&space;=&space;(V,&space;E)$ is a subset $V$ of vertices
• Each pair of vertices is connected by an edge in $E$.
• A clique is a complete sub-graph of $G$
• The size of the clique is the number of vertices it contains

Example

Lets compute the graph from the formula $\phi$ in polynomial time.

• $\phi&space;=&space;(x_{1}&space;\vee&space;\neg&space;x_{2}&space;\vee&space;\neg&space;x_{3}&space;)&space;\wedge&space;(\neg&space;x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)&space;\wedge&space;(x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$

Steps

First draw a graph $G$ derived from the formula $\phi$ where:

• $c_{1}&space;=&space;(x_{1}&space;\vee&space;\neg&space;x_{2}&space;\vee&space;\neg&space;x_{3}&space;)$
• $c_{2}&space;=&space;(\neg&space;x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$
• $c_{3}&space;=&space;(x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$
1. Connect $c_{1}(x_{1})$ to $c_{2}(x_{2},&space;x_{3})$ and $c_{3}(x_{1},x_{2},&space;x_{3})$
2. Connect $c_{1}(\neg&space;x_{2})$ to $c_{2}(\neg&space;x_{1},&space;x_{3})$ and $c_{3}(x_{1},&space;x_{3})$
3. Connect $c_{1}(\neg&space;x_{3})$ to $c_{2}(\neg&space;x_{1},&space;x_{2})$ and $c_{3}(x_{1},&space;x_{2})$
4. Connect $c_{2}(\neg&space;x_{1})$ to $c_{1}(x_{2},&space;x_{3})$
5. Connect $c_{2}(x_{2})$ to $c_{3}(x_{1},&space;x_{2},&space;x_{3})$
6. Connect $c_{2}(x_{3})$ to $c_{3}(x_{1},&space;x_{2},&space;x_{3})$
7. Done