10
$\begingroup$

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?

$\endgroup$
  • 2
    $\begingroup$ What did you find confusing about the results? $\endgroup$ – Niel de Beaudrap Jul 22 '14 at 16:24
  • $\begingroup$ I see different definitions, like some says: The bipartite graph between clauses and the literals must be planar (i don't know by literals do they mean only x_i's or both x_i and its negation, I mean i don't know what is their gadget graph exactly here?). Some other define two types for it: only the bipartite edges between clauses and literals, or these plus (x_i, ~x_i). Or some other says, the above graph plus the (x_i,x_{i+1})'s? I can not even find the original paper published on it? Basically I can not find a good reference with a perfect definition for it? $\endgroup$ – user24175 Jul 22 '14 at 16:43
  • 4
    $\begingroup$ The original reference is: D. Lichtenstein, "Planar formulae and their uses" (1982); but there are many small variations that are still NP-complete (the NPC proof of most of them is easy). $\endgroup$ – Marzio De Biasi Jul 22 '14 at 18:02
  • 1
    $\begingroup$ @Marzio De Biasi Thank you so much! But, based on this paer, planar 3-SAT is the case that the bipartite graph between the clauses that literals (only x_i's not their negations) is planar. Right? We can easily conclude the case that we include also the negation of x_i's just by adding an edge between them, without disturbing the planarity, right? $\endgroup$ – user24175 Jul 22 '14 at 18:38
  • 1
    $\begingroup$ @tinLoaf: as cited in the very good lecture linked by David Eppstein in his answer, you can look at Mark de Berg and Amirali Khosravi, Optimal Binary Space Partitions in the Plane; in which it is proved that monotone planar 3-SAT is NPC: variables are placed on a horizontal line, all positive clauses are drawn above, all negative clauses are drawn below; in that representation it is easy to replace each variable $x_i$ with two stacked (and also linked) literals, the positive literal $+x_i$ above, the negative literal $-x_i$ below, without breaking planarity condition. $\endgroup$ – Marzio De Biasi Jan 14 '16 at 21:47
12
$\begingroup$

There's a nice compilation of definitions of related NP-complete planar satisfiability problems at http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf

One of them, planar monotone 3-sat, allows you to split each terminal into positive and negative, with the terminals placed along a line with the positive part on one side of the line and the negative part on the other side of the line. The clauses have only positive or only negative terminals and are placed on the positive or negative side of the line respectively.

$\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.