Conditions de planarité pour Planar 1-in-3 SAT

Planar 3SAT est NP-complet. Une instance planaire 3SAT est une instance 3SAT pour laquelle le graphique construit à l'aide des règles suivantes est planaire:

1. ajouter un sommet pour chaque et ¯ x $x_i$$\bar{x_i}$
2. ajouter un sommet pour chaque clause$C_j$
3. ajouter un bord pour chaque paire$(x_i,\bar{x_i})$
4. ajouter une arête du sommet (ou ) à chaque sommet qui représente une clause qui le contient$x_i$$\bar{x_i}$
5. ajouter des bords entre deux variables consécutives $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

En particulier, la règle 5 construit une "épine dorsale" qui divise les clauses en deux régions distinctes.

Planar 1-in-3 SAT est également NP-complet.

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

Oui, vous pouvez. En fait, vous pouvez même montrer que quelque chose de plus fort est vrai. Le problème connu sous le nom de Positive Planar 1-in-3-SAT est NP-complet comme le montrent Mulzer et Rote .

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

• vous avez trois variables par clause, aucune d'entre elles n'est niée
• le graphe de la formule est plan, même si vous ajoutez le "backbone" entre les sommets variables

La réduction est de Planar 3-SAT .