Information Technology Reference
In-Depth Information
those literals and is
satisfied
by a truth assignment if and only if at least one of
its members is true under that assignment.
An instance of PLANAR 3SAT is a collection
C
=
{c
1
,c
2
,...,c
m
}
of clauses
over
U
such that (i)
|c
j
|
=3or
|c
j
|
=2foreach
c
j
∈ C
and (ii) the bipartite
graph
B
=(
V,E
), where
V
=
U ∪ C
and
E
contains exactly those pairs
{x, c}
such that either literal
, is planar.
The PLANAR 3SAT problem asks whether there exists some truth assign-
ment for
x
or
x
belongs to the clause
c
U
that simultaneously satisfies all the clauses in
C
. This problem is
known to be NP-
ha
rd. For
examp
le,
U
=
{x
1
,x
2
,x
3
,x
4
}
,
C
=
{c
1
,c
2
,c
3
,c
4
}
,
and
pro-
vide an instance of PLANAR 3SAT. For this instance, the answer is “yes”, since
there is a truth assignment (
c
1
=
{x
1
,x
2
, x
3
}
,
c
2
=
{x
1
, x
2
,x
4
}
,
c
3
=
{x
1
,x
3
, x
4
}
,
c
4
=
{x
2
, x
3
, x
4
}
1) satisfying all clauses. It is
known that PLANAR 3SAT is NP-complete even if each variable occurs exactly
once positively and exactly twice negatively in
x
1
,x
2
,x
3
,x
4
)=(1
,
0
,
1
,
C
[
3
].
3.2 Transformation from a 3SAT-instance to a Polyomino
x
i
∈{x
1
,x
2
,...,x
n
}
Each variable
is transformed to a polyomino of 29 cells
shown in Fig.
4
(a). This poly
om
ino is called a
variable gadget
. The cells labeled
with B and C correspond to
x
i
.
There are four possible variant forms of this gadget; cells B and C and their
adjacent cells may be connected to the opposite side (see dotted cells of Fig.
4
a).
Later, one can see that (a) if two guards are placed on cells B and C, then
x
i
= 1, and (b) if a guard is placed on cell A, then
x
i
, while the cell labeled with A corresponds to
x
i
= 1 (see Fig.
5
). (In this
paper, a guard placed on an arbitrary point on and inside the boundary of cell
g
is simply called a
guard on cell g
or a
guard g
.)
Lemma 1.
(i) There is no five-guard set covering the variable gadget. (ii) There
is a six-guard set covering the variable gadget such that two of the six guards are
g
2
B
B
B
x
i
g
1
A
A
RS T
x
i
x
i
x
i
X
UVW
x
i
g
3
C
(a)
C
C
(b)
Fig. 4.
(a) Variable gadget of 29 cells transformed from
x
i
. There are four variant
forms of this gadget; cells B and C and their adjacent cells may be connected to the
opposite side (see dotted cells). (b) The fourth and fifth guards are needed in R,S,T
and U,V,W for covering T and W, respectively. These two guards cannot cover X.
Search WWH ::
Custom Search