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 = (V, 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 = (x_{1} \vee \neg x_{2} \vee \neg x_{3} ) \wedge (\neg x_{1} \vee x_{2} \vee x_{3} ) \wedge (x_{1} \vee x_{2} \vee x_{3} )$

Steps

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

$c_{1} = (x_{1} \vee \neg x_{2} \vee \neg x_{3} )$
$c_{2} = (\neg x_{1} \vee x_{2} \vee x_{3} )$
$c_{3} = (x_{1} \vee x_{2} \vee x_{3} )$

Connect $c_{1}(x_{1})$ to $c_{2}(x_{2}, x_{3})$ and $c_{3}(x_{1},x_{2}, x_{3})$
Connect $c_{1}(\neg x_{2})$ to $c_{2}(\neg x_{1}, x_{3})$ and $c_{3}(x_{1}, x_{3})$
Connect $c_{1}(\neg x_{3})$ to $c_{2}(\neg x_{1}, x_{2})$ and $c_{3}(x_{1}, x_{2})$
Connect $c_{2}(\neg x_{1})$ to $c_{1}(x_{2}, x_{3})$
Connect $c_{2}(x_{2})$ to $c_{3}(x_{1}, x_{2}, x_{3})$
Connect $c_{2}(x_{3})$ to $c_{3}(x_{1}, x_{2}, x_{3})$
Done

Leave a Reply Cancel reply

Click to Insert Smiley