14
$\begingroup$

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})$ ?
$\endgroup$
  • 1
    $\begingroup$ Just in case if anyone would be looking for the paper where they show hardness of Planar 1-in-3SAT (less stronger version). Here is a link: dl.acm.org/citation.cfm?doid=1137856.1137859 From their proof one can see that the "backbone" requirement is easily met. $\endgroup$ – sud03r Mar 22 '17 at 3:44
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.