Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00130
NPcompleteness of the Planar Separator Problems
Vol. 10, no. 2, pp. 317328, 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 NPcomplete 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 NPcomplete or not.
In this paper, we prove that the Vertex Separator Problem is in
fact NPcomplete when G is a vertex weighted planar graph. The
Edge Separator Problem will be shown NPcomplete 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
NPcomplete 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 NPcompleteness for each such real
number α.

Journal Supporters
