Information Technology Reference
In-Depth Information
three colors are needed to color the vertices of a triangle and the variable triangles have a
vertex labeled
ν
in common, assume without loss of generality that this common vertex has
color 2. The other two vertices in each variable triangle are assigned value 0 or 1, values we
give to the associated variable and its complement.
Consider now the coloring of clause triangles. Since three colors are needed to color
vertices of a clause triangle, consider vertices with colors 0 and 1. The edges between these
clause vertices and the corresponding vertices in variable triangles have different colors at
each end. Let the literals in the clause triangles be given values that are the Boolean comple-
ment of their colors. This provides values for literals that are consistent with the values of
variables and insures that not all literals in a clause have the same value. The third vertex in
each triangle has color 2. Give its literal a value consistent with the value of its variable. It
follows that the clauses are a “Yes” instance of
NAESAT
.
Suppose, on the other hand, that a set of clauses is a “Yes” instance of
NAESAT
.We
show that the graph
G
i
s three-colorable. Assign color 2 to vertex
ν
and colors 0 and 1 to
vertices labeled
x
i
and
x
i
based on the values of these liter
a
ls in the “Yes” instance. Consider
two literals in clau
se
c
j
that are not both satisfied. If
x
i
(
x
i
) is one of these, give the
ve
rtex
labeled
(
j
,
x
i
)
(
(
j
,
x
i
)
) the value that is the Boolean complement of the color of
x
i
(
x
i
)in
its variable triangle. Do the same for the other literal. Since the third literal has the same
value as one of the other two literals (they have different values), let its vertex have color 2.
Then
G
is three-colorable. Thus,
G
is a “Yes” instance of 3-
COLORING
if and only if the
corresponding set of clauses is a “Yes” instance of
NAESAT
.
EXACT COVER
Instance:
Aset
S
=
{
u
1
,
u
2
,
...
,
u
p
}
and a family
{
S
1
,
S
2
,
...
,
S
n
}
of subsets of
S
.
Answer:
“Yes” if there are disjoint subsets
S
j
1
,
S
j
2
,
...
,
S
j
t
such that
∪
≤i≤t
S
j
i
=
S
.
1
THEOREM
8.10.5
EXACT COVER
is
NP
-complete.
Proof
It is straightforward to show that
EXACT COVER
is in
NP
. An NDTM can simply
select the subsets and then verify in time polynomial in the length of the input that these
subsets are disjoint and that they cover the set
S
.
Wenowgivealog-spacereductionfrom3-
COLORING
to
EXACT COVER
.Givenan
instance of 3-
COLORING
,thatis,agraph
G
=(
V
,
E
)
, we construct an instance of
EXACT
COVER
, namely, a set
S
and a family of subsets of
S
such that
G
is a “Yes” instance of
3-
COLORING
if and only if the family of sets is a “Yes” instance of
EXACT COVER
.
As the set
S
we choose
S
=
V
∪{
<e
,
i>
|
e
∈
E
,0
≤
i
≤
}
2
and as the family
of subsets of
S
we choose the sets
S
v
,
i
and
R
e
,
i
defined below for
v
∈
V
,
e
∈
E
and
≤
i
≤
0
2:
S
v
,
i
=
{
v
}∪{
<e
,
i>
|
e
is incident on
v
∈
V
}
}
Let
G
be three-colorable. Then let
c
v
, an integer in
R
e
,
i
=
{
<e
,
i>
{
0, 1, 2
}
,bethecolorofvertex
v
.
We show that the subsets
S
v
,
c
v
for
v
∈
V
and
R
e
,
i
for
<e
,
i>
∈
S
v
,
c
v
for any
v
∈
V
are an exact cover. If
e
=(
v
,
w
)
=
c
w
and
S
v
,
c
v
and
S
w
,
c
w
are disjoint. By
definition the sets
R
e
,
i
are disjoint from the other sets. Furthermore, every element of
S
is
in one of these sets.
On the other hand, suppose that
S
has an exact cover. Then, for each
v
∈
E
,then
c
v
∈
V
,thereisa
unique
c
v
,0
≤
c
v
≤
2, such that
v
∈
S
v
,
c
v
. To show that
G
has a three-coloring, assume
Search WWH ::
Custom Search