Information Technology Reference
In-Depth Information
C 1 =( x 1 ∨ x 1 ∨ x 2 )
C 2 =( x 2 ∨ x 3 ∨ x 5 )
C 3 =( x 3 ∨ x 4 ∨ x 5 )
C 4 =( x 2 ∨ x 5 ∨ x 6 )
C 5 =( x 2 ∨ x 3 ∨ x 4 )
C 6 =( x 2 ∨ x 4 ∨ x 6 )
C 7 =( x 1 ∨ x 2 ∨ x 6 )
(a) Monotone rectilinear representation of a formula ˕
C 4
C 3
C 1
C 2
x 1
x 2
x 3
x 4
x 5
x 6
C 5
C 6
C 7
C 4
C 3
C 2
C 1
x 1
x 2
x 3
x 4
x 5
x 6
C 5
C 6
C 7
(b) Sketch of the clause blocks laid on top of the grid {Q 0 , Q 1 } (empty columns omitted)
Fig. 4. Illustration of the
NP
-hardness reduction
proper grid-like embedding. We call
the base grid and the n special cells
between rows m and m +1the variable cells of the base grid.
Next we augment the pair of partitions
{Q 0 ,
Q 1 }
{Q 0 ,
Q 1 }
by additional blocks, one for each
clause, where positive clauses are added to
Q 1 . The defini-
tion of these clause blocks closely follows the layoutofthegiven MRR, see Fig.4(a).
Let C 1 ,C 2 ,...,C l be the positive clauses of ˕ ordered so that if C i is nested inside
the E-shape of C j in the given MRR then i<j .Analogously let C l +1 ,...,C m be
the ordered negative clauses. We describe the definition of the block B i for a positive
clause C i (1 ≤ i ≤ l ); blocks for negative clauses are defined symmetrically. We create
an intermediate embedding of B i (which is not yet strong but serves as a template for
a later strong embedding)byputting B i on top of the base grid 2
Q 0 and negative clauses to
and adding new ele-
ments to B i and to certain edgeblocksin
Q 1 .Thisfixes B i to runthrough two mirrored
E-shaped sets of grid cells of our choice (Fig.4(b)).Intheupper half of the base grid,
B i is assigned to run between rows m
i +1.Furthermore, B i is assigned
to three columns leading towards the variable cells from the top. Let x j beavariable
contained in C i and assume that C i is the k -th positive clause from the right connecting
to x j in the embedding of the given MRR. Then B i runs between columns jm
i and m
k and
2
Theideaoffixing paths to an underlyinggrid is inspired by Chaplick et al. [7].
Search WWH ::




Custom Search