The Complexity of Planar Counting Problems
<|reference_start|>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 \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.<|reference_end|>
@article{hunt1998the,
    title={The Complexity of Planar Counting Problems},
    author={Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, Richard
  E. Stearns},
    journal={arXiv preprint arXiv:cs/9809017},
    year={1998},
    archivePrefix={arXiv},
    eprint={cs/9809017},
    primaryClass={cs.CC cs.DM}
}