Planarity conditions for Planar 1-in-3 SAT

Problem Detail: 

Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:

1. add a vertex for every $x_i$ and $\bar{x_i}$
2. add a vertex for every clause $C_j$
3. add an edge for every $(x_i,\bar{x_i})$ pair
4. add an edge from vertex $x_i$ (or $\bar{x_i}$) to each vertex that represent a clause that contains it
5. add edges between two consecutive variables $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

In particular, rule 5 builds a "backbone" that splits the clauses in two distinct regions.

Planar 1-in-3 SAT is NP-complete, too.

But for planar 1-in-3 SAT are the planarity conditions defined in the same way as in Planar 3SAT ? In particular, can we assume that there is a backbone that links the variables $(x_i,x_{i+1})$ ?

Asked By : Vor

Answered By : A.Schulz

Yes you can. Actually you can even show that something stronger is true. The problem know as Positive Planar 1-in-3-SAT is NP-complete as shown by Mulzer and Rote.

In this version of 1-in-3-SAT, you require for every input formula that

• you have three variables per clause, none of them negated
• the graph of the formula is planar, even if you add the "backbone" between the variable vertices

The reduction is from Planar 3-SAT.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4826