Planaritätsbedingungen für planares 1-in-3-SAT

Planar 3SAT ist NP-vollständig. Eine planare 3SAT-Instanz ist eine 3SAT-Instanz, für die das unter Verwendung der folgenden Regeln erstellte Diagramm planar ist:

1. fügen Sie einen Eckpunkt für jeden und ¯ x $x_i$$\bar{x_i}$
2. füge einen Vertex für jede Klausel $C_j$
3. Addiere eine Kante für jedes $(x_i,\bar{x_i})$ Paar
4. Addiere eine Kante von Vertex (oder ¯ x $x_i$$\bar{x_i}$ ) zu jedem Scheitelpunkt hinzu, der eine Klausel darstellt, die ihn enthält
5. füge Kanten zwischen zwei aufeinander folgenden Variablen $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

Insbesondere bildet Regel 5 ein "Rückgrat", das die Klauseln in zwei unterschiedliche Regionen aufteilt.

Planar 1-in-3 SAT ist ebenfalls NP-vollständig.

Sind die Planaritätsbedingungen für planares 1-in-3-SAT jedoch wie in Planar 3SAT definiert? Können wir insbesondere davon ausgehen, dass es ein Backbone gibt, das die Variablen verknüpft ? $(x_i,x_{i+1})$

Ja, du kannst. Man kann sogar beweisen, dass etwas Stärkeres wahr ist. Das als Positive Planar 1-in-3-SAT bekannte Problem ist NP-vollständig, wie von Mulzer und Rote gezeigt .

In dieser Version von 1-in-3-SAT benötigen Sie für jede Eingabeformel das

• Sie haben drei Variablen pro Klausel, von denen keine negiert wird
• Das Diagramm der Formel ist eben, auch wenn Sie das "Backbone" zwischen den variablen Scheitelpunkten hinzufügen

Die Reduktion ist von Planar 3-SAT .