We draw a graph in which each clause is represented by a group of three vertices
and each literal is associated with one of the vertices (Figure 14.3).
For each vertex in a group, we put in an edge to all vertices of the other
groups, unless the two associated literals are complements. So in Figure 14.3 we
draw an edge † from
to (x 3 ) 2 , and from
to (x 3 ) 3 , but not from
to
(x 2 ) 2 . Figure 14.3 shows a subset of the edges (the full set looks very messy).
Notice that the subgraph with vertices
, (x 3 ) 2 , (x 3 ) 3 , and (x 1 ) 4 is a 4-clique
and that
is a variable assignment that satisfies e.
This approach can be generalized for any 3SAT expression with k clauses. It
can be shown that the 3SAT problem can be satisfied if and only if the associated
graph has a k-clique. Furthermore, it is not hard to see that the transformation