Answers are grounded in this paper and cite their sources.
Demonstrates the #P-hardness and NP-completeness of various planar counting problems, indicating significant complexity.
We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover. We also prove the NP-completeness of the Ambiguous Satisfiability} problems [J. B. Saxe, Two Papers on Graph Embedding Problems, Tech. Report CMU-CS-80-102, Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 1980] and the DP-completeness (with respect to random polynomial reducibility) of the unique satisfiability problems [L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions, in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 458--463] associated with several of the above problems, when restricted to planar instances. Previously, very few #P}-hardness results, no { NP}-hardness results, and no DP-completeness results were known for counting problems, ambiguous satisfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances. Assuming { P ≠ NP, one corollary of the above results is that there are noε$-approximation algorithms for the problems of maximizing or minimizing a linear objective function subject to a planar system of linear inequality constraints over the integers.
No takes yet. Share an insight, caveat, or question.
Hunt et al. (1998) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: