Java Reference
In-Depth Information
X
1
X
1
X
1
X
2
X
2
X
3
X
3
C
1
C
2
C
3
Figure17
.6
The graph generated from Boolean expression B = (x
1
+x
2
)(x
1
+
x
2
+x
3
)(x
1
+x
3
). Literals from the first clause are labeled C1, and literals from
the second clause are labeled C2. There is an edge between every pair of vertices
except when both vertices represent instances of literals from the same clause, or
a negation of the same variable. Thus, the vertex labeled C1 :y
1
does not connect
to the vertex label
ed
C1 : y
2
(because they are literals in the same clause) or the
vertex labeled C2 :y
1
(because they are opposite values for the same variable).
where k
i
is the number of literals in Clause c
i
. We will transform this to an
instance of K-CLIQUE as follows. We build a graph
G = fv[i;j]j1 i m; 1 j k
i
g;
that is, there is a vertex in G corresponding to every literal in Boolean
expression B. We will draw an edge between each pair of vertices v[i
1
;j
1
]
and v[i
2
;j
2
] unless (1) they are two literals within the same clause (i
1
= i
2
)
or (2) they are opposite values for the same variable (i.e., one is negated
and the other is not). Set k = m. Figure 17.6 shows an example of this
transformation.
B is satisfiable if and only if G has a clique of size k or greater. B being
satisfiable implies that there is a truth assignment such that at least one
literal y[i;j
i
] is true for each i. If so, then these m literals must correspond
to m vertices in a clique of size k = m. Conversely, if G has a clique of
size k or greater, then the clique must have size exactly k (because no two
vertices corresponding to literals in the same clause can be in the clique)
and there is one vertex v[i;j
i
] in the clique for each i. There is a truth
assignment making each y[i;j
i
] true. That truth assignment satisfies B.
We conclude that K-CLIQUE is NP-hard, therefore NP-complete.
2
