Information Technology Reference
In-Depth Information
e
a
c
d
b
f
G
2,
j
,
v
(a)
(b)
(c)
Figure 8.23
Gadgets used to reduce 3-
SAT
to
HAMILTONIAN PATH
.
three literals. Second, construct and interconnect three types of subgraphs (gadgets).
Figures
8.23
(a) and (b) show the first and second of theses gadgets,
G
1
and
G
2
.
There is one first gadget for each variable
x
i
,1
n
, denoted
G
1,
i
.Theleftpath
between the two middle vertices in
G
1,
i
is associated with the value
x
i
=
1andthe
right path is associated with the complementary value,
x
i
=
0. Vertex
f
of
G
1,
i
is
identified with vertex
e
of
G
1,
i
+
1
for 1
≤
i
≤
1, vertex
e
of
G
1,1
is connected only
to a vertex in
G
1,1
,andvertex
f
of
G
1,
n
is connected to the clique described below.
There is one second gadget for each literal in each clause. Thus, if
x
i
(
x
i
)isaliteralin
clause
c
j
, then we create a gadget
G
2,
j
,
i
,1
(
G
2,
j
,
i
,0
).
Since a
HAMILTONIAN PATH
touches every vertex, a path through
G
2,
j
,
i
,
v
for
v
≤
i
≤
n
−
∈
{
passes either from
a
to
c
or from
b
to
d
.
For each 1
0, 1
}
n
the two parallel edges of
G
1,
i
arebro
k
enopenandtwovertices
appear in each of them. For each instance of the literal
x
i
(
x
i
), connect the vertices
a
and
c
of
G
2,
j
,
i
,1
(
G
2,
j
,
i
,0
) to the pair of vertices on the left (right) that are created in
G
1,
i
. Connect the
b
vertex of one literal in clause
c
j
to the
d
vertex of another one, as
suggested in Fig.
8.23
(c).
The third gadget has vertices
g
and
h
and a connecting edge. One of these two vertices,
h
, is connected in a clique with the
b
and
d
vertices of the gadgets
G
2,
j
,
i
,
v
and the
f
vertex of
G
1,
n
.
This graph has a Hamiltonian path between
g
and the
e
vertex of
G
1,1
if and only if
the instance of 3-
SAT
is a “yes” instance.
8.28 Show that the
TRAVELING SALESPERSON
decision problem defined below is
NP
-
complete.
≤
i
≤
TRAVELING SALESPERSON
Instance:
An integer
k
and a set of
n
(
n
−
1
)
/
2distances
{
d
1,2
,
d
1,3
,
...
,
d
1,
n
,
d
2,3
,
...
,
d
2,
n
,
...
,
d
n−
1,
n
}
between
n
cities.
Answer:
“Yes” if there is a
tour
(an ordering)
{
i
1
,
i
2
,
...
,
i
n
}
of the cities such that the
length
l
=
d
i
1
,
i
2
+
d
i
2
,
i
3
+
···
+
d
i
n
,
i
1
of the tour satisfies
l
≤
k
.
Hint:
Tr y r e d u c i n g
HAMILTONIAN PATH
to
TRAVELING SALESPERSON
.
Search WWH ::
Custom Search