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

14

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 iXjeXje¯
  2. ajouter un sommet pour chaque clauseCj
  3. ajouter un bord pour chaque paire(Xje,Xje¯)
  4. ajouter une arête du sommet (ou ) à chaque sommet qui représente une clause qui le contientXjeXje¯
  5. ajouter des bords entre deux variables consécutives (X1,X2),(X2,X3),...,(Xn,X1)

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 ? (Xje,Xje+1)
Vor
la source
1
Juste au cas où quelqu'un chercherait le papier où il présente la dureté de Planar 1-in-3SAT (version moins résistante). Voici un lien: dl.acm.org/citation.cfm?doid=1137856.1137859 D'après leur preuve, on peut voir que l'exigence de «colonne vertébrale» est facilement satisfaite.
sud03r

Réponses:

8

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 .

A.Schulz
la source