NP-completeness of the Planar Separator Problems - Fukuyama, Junichiro (Journal of Graph Algorithms and Applications, 2006)
For a given graph G, the Separator Problem asks whether avertex or edge set of small cardinality (or weight) exists whoseremoval partitions G into two disjoint graphs of approximatelyequal sizes. Called the Vertex Separator Problem when theremoved set is a vertex set, and the Edge Separator Problemwhen it is an edge set, both problems are NP-complete for generalunweighted graphs [].Despite the significance of planar graphs, it has not been knownwhether the Planar Separator Problem, which considers aplanar graph and a threshold as an input, is NP-complete or not.In this paper, we prove that the Vertex Separator Problem is infact NP-complete when G is a vertex weighted planar graph. TheEdge Separator Problem will be shown NP-complete when G is avertex and edge weighted planar graph.In addition, we consider how to treat the constant α ∈ R+ of the α-Separator Problem that partitions Ginto two disjoint graphs of size at most ( 1− α) |V(G) |. The α-Separator Problem is notNP-complete for all real numbers α ∈ (0, 1/2 ],because it would imply uncountably many Non Deterministic TuringMachines. We will present a general scheme for treating a constantin computer arithmetic, by introducing the notion of realnumbers comparable with rationals in polynomial time. Thisapproach allows us to prove NP-completeness for each such realnumber α. <!---->