Information Technology Reference
In-Depth Information
g
1
g
3
B
B
r
x
i
x
i
g
2
g
4
g
2
A
A
v
x
i
x
i
x
i
x
i
s
t
s
t
g
5
g
5
u
u
g
4
v
x
i
x
i
r
g
3
g
1
C
C
(a)
(b)
Fig. 6.
There does not exist a six-guard set covering the variable gadget such that two
of the guards are placed on A and B or on A and C.
c
1
x
1
x
2
x
3
(a)
(b)
Fig. 7.
(a) Clause gadget of five cells transformed from
c
1
=
{x
1
,x
2
, x
3
}
. (b) If a clause
consists of two literals, then the corresponding clause gadget is composed of three cells.
Each clause
c
j
∈{c
1
,c
2
,...,c
m
}
is transformed into a
clause gadget
of
5
c
j
has three literals (see Fig.
7
a). The first, third, and fifth cells
are labeled with the three literals of
×
1 cells if
c
j
. Those three cells are connected to the
corresponding variable gadgets (see Fig.
8
). If
c
j
consists of two literals, then the
corresponding clause gadget is composed of 3
1 cells (see Fig.
7
b). (The gad-
get of Fig.
7
(b) is essential, since it is known that 3SAT with exactly three
occurrences per variable is polynomial-time solvable if every clause
×
c
j
has
three literals [
11
].)
In order to construct connections from variable gadgets to clause gadgets, we
use
connection gadgets
(see green cells of Fig.
8
). Each connection gadget has an
even number of bends. (Bending cells are indicated by red spheres in the figure).
For example, the number of bends in the connection gadget between
x
4
and
c
2
(resp.
c
3
) is four (resp. two).
Finally, let
x
4
and
k
=6
n
+
l/
2(=6
·
4+16
/
2 = 32), where
n
is the number of
variables, and
l
is the number of bends in all the connection gadgets. From this
construction,
C
is satisfiable if and only if the whole polyomino
P
is covered by
k
guards. From the positions of the 32 guards, one can see that (
x
1
,x
2
,x
3
,x
4
)=
,
,
,
C
(1
0
1
1) satisfies
. This completes the proof.
Search WWH ::
Custom Search