THE COMPLEXITY OF PLANAR COUNTING PROBLEMS

We prove the #P-hardness of the counting problems associated with vari ous satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3SAT, 1-3SAT, 1-EX3SAT, M INIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM Feedback Vertex S et, 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, D ept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 1980] and the D-P-completeness (with respect to random polynomial reducibil ity) of the unique satisfiability problems [L. G. Valiant and V. V. Va zirani, NP is as easy as detecting unique solutions, in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 458-463] associated with seve ral of the above problems, when restricted to planar instances. Previo usly, very few #P-hardness results, no NP-hardness results, and no D-P -completeness results were known for counting problems, ambiguous sati sfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances. Assuming P not equal NP, one cor ollary of the above results is that there are no epsilon-approximation algorithms for the problems of maximizing or minimizing a linear obje ctive function subject to a planar system of linear inequality constra ints over the integers.