Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00130
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 α.
|
Journal Supporters
|