Information Technology Reference
In-Depth Information
...
Q
0
Q
1
...
Fig. 3.
Graph
G
2
,
3
and the partitions
{Q
0
, Q
1
}
sketched for the top-left grid cell marked in gray
to construct a base graph
G
m,n
for two integers
m
and
n
.Thegraph
G
m,n
is a grid
with
mn
+1columns and 2
m
+2rows of vertices with integer coordinates (
i,j
) for
0
2
m
+1. Each vertex
v
with coordinates (
i,j
) is connected to
the four vertices at coordinates (
i
≤
i
≤
mn
and 0
≤
j
≤
1)
,
(
i,j
+1)(if they exist).
Between the middle rows
m
and
m
+1we remove all vertical edges except for those in
columns 0
,m,
2
m,...,nm
. This defines
n
larger grid cells of width
m
in this particular
row. Figure 3 (left) shows an example.
From
G
m,n
we construct a pair of partitions
−
1
,j
)
,
(
i
+1
,j
)
,
(
i,j
−
as follows (see Fig.3).
For each vertex
v
with coordinates (
i,j
) we create a
vertex block
B
v
in partition
Q
(
i
+
j
)(mod2)
. For each edge (
u,v
) in
G
m,n
we create a chain of four
edgeblocks
B
u,v
,
B
u,v
,
B
u,v
,
B
u,v
,such that
B
u,v
and
B
u,v
are in the same partition as
B
v
and
B
u,v
and
B
u,v
are in the same partition as
B
u
. We distribute five distinct elements
among the edgeblocksof(
u,v
) and the vertex blocks for
u
and
v
such that they form
the desired chain pattern and each intersection face contains one common element. The
pair
{Q
0
,Q
1
}
is indeed a pair of partitions as every element belongs to exactly one
block of each partition. Edge blocks contain two and vertex blocks uptofourelements
(depending on the degree of the corresponding vertex in
G
m,n
). Below we will add the
gadgets of the reduction on top of
{Q
0
,
Q
1
}
,forwhichitisrequired that there is an
edge block in each partition that does not share any element with a vertex block. This
explains why we link blocks of adjacent vertices by chains of fourblocks.
The next lemma shows that
{Q
0
,
Q
1
}
has a unique embedding (proof in the full
version [1]), which is a consequence of the fact that
G
m,n
is a subdivision of a planar
3-connected graph (assuming
n
{Q
0
,
Q
1
}
≥
2)andthusithasaunique embedding. This property
is inherited by
{Q
0
,
Q
1
}
in our construction.
Lemma 1.
Thepair of partitions
{Q
0
,
Q
1
}
has auniqueembedding.
Now we have all the tools that we need to prove our main theorem in this section.
Proof (of Theorem 4).
First we show that the problem is in
. By Theorem 2 we know
that a pair of partitions is strongly embeddable if and only if it has a planar support.
Thus we can “guess” a graph on
U
and then test its planarity and support property in
polynomial time. This shows membership in
NP
NP
. It remains to describe the hardness
reduction.
Let
˕
be a planar monotone 3Sat formula together with an MRR. First we construct
the pair of partitions
for the base graph
G
m,n
,where
m
is the number of
clauses of
˕
and
n
is the number of variables of
˕
. By Lemma 1
{Q
0
,
Q
1
}
{Q
0
,
Q
1
}
has a unique
