NP-completeness of the Planar Separator Problems

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 α.