Planar SAT
In computer science, the planar 3-satisfiability problem (abbreviated PLANAR 3SAT or PL3SAT) is an extension of the classical Boolean 3-satisfiability problem to a planar incidence graph. In other words, it asks whether the variables of a given Boolean formula—whose incidence graph consisting of variables and clauses can be embedded on a plane—can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.
Like 3SAT, PLANAR-SAT is NP-complete, and is commonly used in reductions.
Definition
A planar graph is a graph that can be drawn on the plane in a way such that no two of its edges cross each other. Every 3SAT problem can be converted to an incidence graph in the following manner: For every variable , the graph has one corresponding , and for every clause , the graph has one corresponding node We create an edge between variable and clause whenever or is in . We distinguish positive and negative literals using edge colorings.
Planar 3SAT is a subset of 3SAT in which the incidence graph of the variables and the clauses of a Boolean formula is planar. It is important because it is a restricted variant, and is still NP-complete. Many problems (for example games and puzzles) cannot represent non-planar graphs. Hence, Planar 3SAT provides a way to prove those games to be NP-hard.
Proof of NP-completeness
The following proof sketch follows the proof of D. Lichtenstein.[1]
Trivially, PLANAR 3SAT is in NP. It is thus sufficient to show that it is NP-hard via reduction from 3SAT.
First, draw the incidence graph of the 3SAT formula. Since no two variables or clauses are connected, the resulting graph will be bipartite. The resulting graph may not be planar. Replace every crossing of edges with a crossover gadget shown here. However, the figure leads to a minor error—some clauses contain 4 variables and some contain only 2 variables so the premises of 3SAT are not followed exactly in the gadget shown. This glitch is easily fixable: For a clause that only contains 2 variables, either create parallel edges from one variable to the clause or create a separate false variable to include in the constraint.
For the 4 variable clause, borrow the reduction from 4SAT to 3SAT to create a gadget that involves introducing an extra variable set to false which represents whether the left or right side of the original clause contained the satisfying literal. This completes the reduction.[2]
Variants and related problems
- Planar 3SAT with a variable-cycle: Here, in addition to the incidence-graph being planar, the following graph should also be planar: there is a cycle going through all variables, each clause is either inside the cycle or outside it, and linked to its corresponding variables. This problem is NP-complete.[1]
- However, if we further restrict the problem such that all clauses are inside the variable-cycle, or all clauses ar outside it, then the problem can be solved in polynomial time using dynamic programming.
- Planar 3SAT with literals: The bipartite incidence graph of the literals and clauses is planar too. This problem is NP-complete.[1]
- Planar rectilinear 3SAT: Each variable is a horizontal segment on the x-axis while each clause is a horizontal segment above/below the x-axis with vertical connections to the 3 variables it includes on the x-axis. The connections in each clause are either all-positive or all-negative. This problem is NP-complete.[3]
- Planar monotone rectilinear 3SAT: This is a variant of planar rectilinear 3SAT where the clauses above the x-axis are all-positive and the clauses below the x-axis are all-negative. This problem is NP-complete.[4]
- Planar 1-in-3SAT: This is the planar equivalent of 1-in-3SAT. It is NP-complete.[5]
- Planar NAE 3SAT: This problem is planar equivalent of NAE 3SAT. Surprisingly, it can be solved in polynomial time. The proof is by reduction to planar maximum cut.[7]
- Planar circuit SAT: This is a variant of circuit SAT in which the circuit, computing the SAT formula, is a planar directed acyclic graph. Note that this is a different graph than the adjacency graph of the formula. This problem is NP-complete.[8]
Reductions
Shakashaka
Shakashaka is a logic puzzle board game developed by publisher Nikoli. The objective is to fill the white squares in a given grid with a pattern of triangles such that each white area in the resulting grid has a rectangular shape. Furthermore, each black square in the grid marked with a number must be orthogonally adjacent to the specified number of triangles. It has been proven to be NP-complete via a reduction from Planar 3SAT[9]
Flat folding of fixed-angle chains
This is the problem of deciding whether a polygonal chain with fixed edge lengths and angles has a planar configuration without crossings. It has been proven to be strongly NP-hard via a reduction from planar monotone rectilinear 3SAT.[10]
Minimum edge-length partition
This is the problem of partitioning a polygon into simpler polygons such that the total length of all edges used in the partition is as small as possible.
When the figure is a rectilinear polygon and it should be partitioned into rectangles, and the polygon is hole-free, then the problem is polynomial. But if it contains holes (even degenerate holes - single points), the problem is NP-hard, by reduction from Planar SAT. The same holds if the figure is any polygon and it should be partitioned into convex figures.[11]
A related problem is minimum-weight triangulation - finding a triangulation of minimal total edge length. The decision version of this problem is proven to be NP-complete via a reduction from a variant of Planar 1-in-3SAT.[12]
References
- Lichtenstein, David (1982-05-01). "Planar Formulae and Their Uses". SIAM Journal on Computing. 11 (2): 329–343. doi:10.1137/0211025. ISSN 0097-5397.
- Demaine, Eric (2015). "7. Planar SAT". MIT Open CourseWare.
- Raghunathan, Arvind; Knuth, Donald E. (1992). "The problem of compatible representatives". SIAM J. Discrete Math. 5 (3): 422–427. arXiv:cs/9301116. Bibcode:1993cs........1116K. doi:10.1137/0405033.
- De Berg, Mark; Khosravi, Amirali (2010). "Optimal Binary Space Partitions in the Plane". Computing and Combinatorics. Lecture Notes in Computer Science. 6196. pp. 216–225. doi:10.1007/978-3-642-14031-0_25. ISBN 978-3-642-14030-3.
- Dyer, M.E; Frieze, A.M (June 1986). "Planar 3DM is NP-complete". Journal of Algorithms. 7 (2): 174–184. doi:10.1016/0196-6774(86)90002-7.
- Mulzer, Wolfgang; Rote, Günter (2008-05-15). "Minimum-weight triangulation is NP-hard". Journal of the ACM. 55 (2): 11:1–11:29. doi:10.1145/1346330.1346336. ISSN 0004-5411.
- Moret, B. M. E. (June 1988). "Planar NAE3SAT is in P". SIGACT News. 19 (2): 51–54. doi:10.1145/49097.49099. ISSN 0163-5700.
- Demaine, Erik (2015). "6. Circuit SAT". Youtube.
- Demaine, Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Computational complexity and an integer programming model of Shakashaka" (PDF), IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A (6): 1213–1219, Bibcode:2014IEITF..97.1213D, doi:10.1587/transfun.E97.A.1213, hdl:10119/12147
- Demaine, Erik D.; Eisenstat, Sarah (2011). Dehne, Frank; Iacono, John; Sack, Jörg-Rüdiger (eds.). "Flattening Fixed-Angle Chains Is Strongly NP-Hard". Algorithms and Data Structures. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 6844: 314–325. doi:10.1007/978-3-642-22300-6_27. ISBN 9783642223006.
- https://people.csail.mit.edu/rivest/pubs/LPRS82.pdf
- Mulzer, Wolfgang; Rote, Günter (May 2008). "Minimum-weight Triangulation is NP-hard". J. ACM. 55 (2): 11:1–11:29. doi:10.1145/1346330.1346336. ISSN 0004-5411.