The complexity of planar counting problems

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 D-P-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 D-P-completeness results were known for counting problems, ambiguous satisfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances. Assuming P not equal NP, one corollary of the above results is that there are no epsilon-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.