Java Reference
In-Depth Information
Example17.2
In this example, we make use of a simple conversion be-
tween two graph problems.
Theorem17.2
VERTEX COVER is NP-complete.
Proof:
Prove that VERTEX COVER is in NP: Simply guess a subset
of the graph and determine in polynomial time whether that subset is in fact
a vertex cover of size k or less.
Prove that VERTEX COVER is NP-hard: We will assume that K-
CLIQUE is already known to be NP-complete. (We will see this proof in
the next example. For now, just accept that it is true.)
Given that K-CLIQUE is NP-complete, we need to find a polynomial-
time transformation from the input to K-CLIQUE to the input to VERTEX
COVER, and another polynomial-time transformation from the output for
VERTEX COVER to the output for K-CLIQUE. This turns out to be a
simple matter, given the following observation. Consider a graph G and
a vertex cover S on G. Denote by S
0
the set of vertices in G but not in S.
There can be no edge connecting any two vertices in S
0
because, if there
were, then S would not be a vertex cover. Denote by G
0
the inverse graph
for G, that is, the graph formed from the edges not in G. If S is of size
k, then S
0
forms a clique of size nk in graph G
0
. Thus, we can reduce
K-CLIQUE to VERTEX COVER simply by converting graph G to G
0
, and
asking if G
0
has a VERTEX COVER of size nk or smaller. If YES, then
there is a clique in G of size k; if NO then there is not.
2
Example17.3
So far, our NP-completeness proofs have involved trans-
formations between inputs of the same “type,” such as from a Boolean ex-
pression to a Boolean expression or from a graph to a graph. Sometimes an
NP-completeness proof involves a transformation between types of inputs,
as shown next.
Theorem17.3
K-CLIQUE is NP-complete.
Proof:
K-CLIQUE is in NP, because we can just guess a collection of k
vertices and test in polynomial time if it is a clique. Now we show that K-
CLIQUE is NP-hard by using a reduction from SAT. An instance of SAT
is a Boolean expression
B = C
1
C
2
:::C
m
whose clauses we will describe by the notation
C
i
= y[i; 1] + y[i; 2] + ::: + y[i;k
i
]
