Planar SAT

From HandWiki
Graph of the formula (x_1 or not x_2) and (not x_1 or x_2 or not x_3)
Example of a planar SAT problem. The black edges correspond to non-inverted variables and the red edges correspond to inverted variables.

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

Every 3SAT problem can be converted to an incidence graph in the following manner: For every variable [math]\displaystyle{ v_i }[/math], the graph has one corresponding node [math]\displaystyle{ v_i }[/math], and for every clause [math]\displaystyle{ c_j }[/math], the graph has one corresponding node [math]\displaystyle{ c_j. }[/math] An edge [math]\displaystyle{ (v_i, c_j) }[/math] is created between variable [math]\displaystyle{ v_i }[/math] and clause [math]\displaystyle{ c_j }[/math] whenever [math]\displaystyle{ v_i }[/math] or [math]\displaystyle{ \lnot v_i }[/math] is in [math]\displaystyle{ c_j }[/math]. Positive and negative literals are distinguished using edge colorings.

The formula is satisfiable if and only if there is a way to assign TRUE or FALSE to each variable node such that every clause node is connected to at least one TRUE by a positive edge or FALSE by a negative edge.

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. Planar 3SAT is a subset of 3SAT in which the incidence graph of the variables and 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 problems to be NP-hard.

Proof of NP-completeness

Graph with black and red edges
Left side is a crossing; right side is the crossover gadget. The small dots represent clauses. The black and red edges correspond to non-inverted and inverted variables respectively.

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.

This proof makes use of the fact that [math]\displaystyle{ (\lnot a \lor \lnot b \lor c) \land (a \lor \lnot c) \land (b \lor \lnot c) }[/math] is equivalent to [math]\displaystyle{ (a \land b) \leftrightarrow c }[/math] and that [math]\displaystyle{ (a \lor \lnot b) \land (\lnot a \lor b) }[/math] is equivalent to [math]\displaystyle{ a \leftrightarrow b }[/math].

First, draw the incidence graph of the 3SAT formula. Since no two variables or clauses are connected, the resulting graph will be bipartite. Suppose the resulting graph is not planar. For every crossing of edges (a, c1) and (b, c2), introduce nine new variables a1, b1, α, β, γ, δ, ξ, a2, b2, and replace every crossing of edges with a crossover gadget shown in the diagram. It consists of the following new clauses:

[math]\displaystyle{ \begin{array}{ll} (\lnot a_2 \lor \lnot b_2 \lor \alpha) \land (a_2 \lor \lnot \alpha) \land (b_2 \lor \lnot \alpha), &\quad \text{i.e.,} \quad a_2 \land b_2 \leftrightarrow \alpha \\ (\lnot a_2 \lor b_1 \lor \beta) \land (a_2 \lor \lnot \beta) \land (\lnot b_1 \lor \lnot \beta), &\quad \text{i.e.,} \quad a_2 \land \lnot b_1 \leftrightarrow \beta \\ (a_1 \lor b_1 \lor \gamma) \land (\lnot a_1 \lor \lnot \gamma) \land (\lnot b_1 \lor \lnot \gamma), &\quad \text{i.e.,} \quad \lnot a_1 \land \lnot b_1 \leftrightarrow \gamma \\ (a_1 \lor \lnot b_2 \lor \delta) \land (\lnot a_1 \lor \lnot \delta) \land (b_2 \lor \lnot \delta), &\quad \text{i.e.,} \quad \lnot a_1 \land b_2 \leftrightarrow \delta \\ (\alpha \lor \beta \lor \xi) \land (\gamma \lor \delta \lor \lnot \xi), &\quad \text{i.e.,} \quad \alpha \lor \beta \lor \gamma \lor \delta \\ (\lnot\alpha \lor \lnot\beta) \land (\lnot\beta \lor \lnot\gamma) \land (\lnot\gamma \lor \lnot\delta) \land (\lnot\delta \lor \lnot\alpha), &\\ (a_2 \lor \lnot a) \land (a \lor \lnot a_2) \land (b_2 \lor \lnot b) \land (b \lor \lnot b_2), &\quad \text{i.e.,} \quad a \leftrightarrow a_2, ~ b \leftrightarrow b_2 \\ \end{array} }[/math]

If the edge (a, c1) is inverted in the original graph, (a1, c1) should be inverted in the crossover gadget. Similarly if the edge (b, c2) is inverted in the original, (b1, c2) should be inverted.

One can easily show that these clauses are satisfiable if and only if [math]\displaystyle{ a \leftrightarrow a_1 }[/math] and [math]\displaystyle{ b \leftrightarrow b_1 }[/math].

This algorithm shows that it is possible to convert each crossing into its planar equivalent using only a constant amount of new additions. Since the number of crossings is polynomial in terms of the number of clauses and variables, the reduction is polynomial.[2]

Variants and related problems

  • Planar 3SAT with a variable-cycle: Here, in addition to the incidence-graph, the graph also includes a cycle going through all the variables, and each clause is either inside or outside this cycle. The resulting graph must still be planar. This problem is NP-complete.[1]
    • However, if the problem is further restricted such that all clauses are inside the variable-cycle, or all clauses are 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: Vertices of the graph are represented as horizontal segments. Each variable lies on the x-axis while each clause lies above/below the x-axis. Every connection between a variable and a clause must be a vertical segment. Each clause may only have up to 3 connections with variables and 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] and remains NP-complete when each clause containing three variables has two neighboring variables that are adjacent on the x-axis (i.e., no other variable appears horizontally between the neighboring variables).[5]
  • Planar 1-in-3SAT: This is the planar equivalent of 1-in-3SAT. It is NP-complete.[6]
    • Planar positive rectilinear 1-in-3SAT: This is the planar equivalent of positive 1-in-3SAT. It is NP-complete.[7]
  • Planar NAE 3SAT: This problem is the planar equivalent of NAE 3SAT. Unlike the other variants, this problem can be solved in polynomial time. The proof is by reduction to planar maximum cut.[8]
  • 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.[9]

Reductions

Logic puzzles

Reduction from Planar SAT is a commonly used method in NP-completeness proofs of logic puzzles. Examples of these include Fillomino,[10] Nurikabe,[11] Shakashaka,[12] Tatamibari,[13] and Tentai Show.[14] These proofs involve constructing gadgets that can simulate wires carrying signals (Boolean values), input and output gates, signal splitters, NOT gates and AND (or OR) gates in order to represent the planar embedding of any Boolean circuit. Since the circuits are planar, crossover of wires do not need to be considered.

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.[15]

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.[16]

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.[17]

References

  1. ↑ 1.0 1.1 1.2 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. https://epubs.siam.org/doi/10.1137/0211025. 
  2. ↑ Demaine, Eric (2015). "7. Planar SAT". https://www.youtube.com/watch?v=KU8I8LjnQgE. 
  3. ↑ Raghunathan, Arvind; Knuth, Donald E. (1992). "The problem of compatible representatives". SIAM J. Discrete Math. 5 (3): 422–427. doi:10.1137/0405033. Bibcode: 1993cs........1116K. 
  4. ↑ 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. 
  5. ↑ Agarwal, Pankaj K.; Aronov, Boris; Geft, Tzvika; Halperin, Dan (2021). "On Two-Handed Planar Assembly Partitioning with Connectivity Constraints". Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA): 1740–1756. doi:10.1137/1.9781611976465.105. ISBN 978-1-61197-646-5. 
  6. ↑ 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. 
  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. https://doi.org/10.1145/1346330.1346336. 
  8. ↑ 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. https://www.cs.unm.edu/~moret/nae3sat.ps. 
  9. ↑ Demaine, Erik (2015). "6. Circuit SAT". https://www.youtube.com/watch?v=ziViLYrf1Ak. 
  10. ↑ Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. 
  11. ↑ Holzer, Markus; Klein, Andreas; Kutrib, Martin (2004). "On The NP-Completeness of The NURIKABE Pencil Puzzle and Variants Thereof". Proceedings of the 3rd International Conference on Fun with Algorithms. https://pdfs.semanticscholar.org/4855/b7160c651c8cc883def72348463fd77cdbed.pdf. 
  12. ↑ Demaine, Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Computational complexity and an integer programming model of Shakashaka", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97-A (6): 1213–1219, doi:10.1587/transfun.E97.A.1213, Bibcode: 2014IEITF..97.1213D, https://dspace.mit.edu/bitstream/1721.1/99994/1/Demaine_Computational%20complexity.pdf 
  13. ↑ Adler, Aviv; Bosboom, Jeffrey; Demaine, Erik D.; Demaine, Martin L.; Liu, Quanquan C.; Lynch, Jayson (7 May 2020). "Tatamibari is NP-complete". arXiv:2003.08331 [cs.CC].
  14. ↑ Fertin, Guillaume; Jamshidi, Shahrad; Komusiewicz, Christian (June 2015). "Towards an Algorithmic Guide to Spiral Galaxies". Theoretical Computer Science 586: 26–39. doi:10.1016/j.tcs.2015.01.051. https://hal.archives-ouvertes.fr/hal-01159940. Retrieved 18 August 2021. 
  15. ↑ Demaine, Erik D.; Eisenstat, Sarah (2011). "Flattening Fixed-Angle Chains is Strongly NP-Hard". in Dehne, Frank; Iacono, John; Sack, Jörg-Rüdiger. Algorithms and Data Structures. Lecture Notes in Computer Science. 6844. Springer Berlin Heidelberg. pp. 314–325. doi:10.1007/978-3-642-22300-6_27. ISBN 9783642223006. 
  16. ↑ Lingas, Andrzej; Pinter, Ron Y.; Rivest, Ronald L.; Shamir, Adi (1982). "Minimum edge length partitioning of rectilinear polygons". Proc. 20th Allerton Conf. Commun. Control Comput: 53–63. https://people.csail.mit.edu/rivest/pubs/LPRS82.pdf. 
  17. ↑ 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. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Planar_SAT&oldid=3368521"