NP-completeness of the Planar Separator Problems
Vol. 10, no. 2, pp. 317-328, 2006. Regular paper.
Abstract For a given graph
G, the
Separator Problem asks whether a
vertex or edge set of small cardinality (or weight) exists whose
removal partitions
G into two disjoint graphs of approximately
equal sizes. Called the
Vertex Separator Problem when the
removed set is a vertex set, and the
Edge Separator Problem
when it is an edge set, both problems are
NP-complete for general
unweighted graphs [].
Despite the significance of planar graphs, it has not been known
whether the
Planar Separator Problem, which considers a
planar graph and a threshold as an input, is
NP-complete or not.
In this paper, we prove that the Vertex Separator Problem is in
fact
NP-complete when
G is a vertex weighted planar graph. The
Edge Separator Problem will be shown
NP-complete when
G is a
vertex and edge weighted planar graph.
In addition, we consider how to treat the constant α ∈
R+ of the
α-Separator Problem that partitions
G
into two disjoint graphs of size at most ( 1− α) |
V(
G) |. The α-Separator Problem is not
NP-complete for all real numbers α ∈ (0, 1/2 ],
because it would imply uncountably many Non Deterministic Turing
Machines. We will present a general scheme for treating a constant
in computer arithmetic, by introducing the notion of
real
numbers comparable with rationals in polynomial time. This
approach allows us to prove NP-completeness for each such real
number α.