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 \begin{ romannum} \item[{ }] { \sc 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover.} \end{ romannum} We also prove the { \sf NP}-completeness of the { \sc Ambiguous Satisfiability} problems \cite{ Sa80} and the { \sf D$^P$}-completeness (with respect to random polynomial reducibility) of the unique satisfiability problems \cite{ VV85} associated with several of the above problems, when restricted to planar instances. Previously, very few { \sf #P}-hardness results, no { \sf NP}-hardness results, and no { \sf D$^P$}-completeness results were known for counting problems, ambiguous satisfiability problems and unique satisfiability problems, respectively, when restricted to planar instances. Assuming { \sf P $\neq $ NP}, one corollary of the above results is 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.
Categories: cs.CC cs.DM