Planarity conditions for Planar 1-in-3 SAT

ignougroup
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