Geodesic
NP-completeness of the Planar Separator Problems
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 317-328.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 α.
DOI : 10.7155/jgaa.00130
Keywords: graph partitioning, planar separator theorem, NP-completeness, vertex separator, edge separator 
@article{JGAA_2006_10_2_a10,
     author = {Junichiro Fukuyama},
     title = {NP-completeness of the {Planar} {Separator} {Problems}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {317--328},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00130},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00130/}
}
TY  - JOUR
AU  - Junichiro Fukuyama
TI  - NP-completeness of the Planar Separator Problems
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 317
EP  - 328
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00130/
DO  - 10.7155/jgaa.00130
LA  - en
ID  - JGAA_2006_10_2_a10
ER  - 
%0 Journal Article
%A Junichiro Fukuyama
%T NP-completeness of the Planar Separator Problems
%J Journal of Graph Algorithms and Applications
%D 2006
%P 317-328
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00130/
%R 10.7155/jgaa.00130
%G en
%F JGAA_2006_10_2_a10
Junichiro Fukuyama. NP-completeness of the Planar Separator Problems. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 317-328. doi : 10.7155/jgaa.00130. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00130/

Cité par Sources :