conditions de planéité pour Planar 1-en-3 SAT

Question

Planar 3SAT est NP-complet. Une instance de 3SAT plane est une instance de 3SAT pour lequel le graphe construit selon les règles suivantes est plane:

1. ajouter un sommet pour chaque x_i $ $ et $ \ bar {x_i} $
2. ajouter un sommet pour chaque article $ $ C_J
3. ajouter un avantage pour chaque $ (x_i, \ bar {} x_i) $ paire
4. ajouter un bord de sommet $ x_i $ (ou $ \ bar {} x_i $) à chaque sommet qui représentent une clause qui contient
5. ajouter des bordures entre deux variables consécutives $ (de x 1, x 2), (x 2, x_3), ..., (x_n, x 1) $

, la règle 5 En particulier construit un « squelette » qui sépare les articles dans deux régions distinctes.

Planar 1-en-3 SAT est NP-complet, aussi.

Mais pour plan 1 en 3 SAT sont les conditions définies dans la planéité même manière que dans Planar 3SAT? En particulier, peut-on supposer qu'il ya une épine dorsale qui relie les $ variables (x_i, x_ {i + 1}) $?

Answer 1

Oui, vous pouvez. En fait, vous pouvez même montrer que quelque chose est vrai fort. Le savoir problème Positive Planar 1 en 3-SAT est NP-complet comme le montre Mulzer et Rote .

vous avez besoin pour chaque formule d'entrée Dans cette version de 1-en-3-SAT, que

• vous avez trois variables par clause, aucun d'entre eux niée
• le graphe de la formule est plane, même si vous ajoutez la « colonne vertébrale » entre les sommets variable

La réduction est de Planar 3-SAT .