Abstract. 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 [23] and the D Pcompleteness (with respect to random polynomial reducibility) of the unique satisfiability problems [27] 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 = NP, one corollary of the above results is (i) 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. Key words. planar, 3Sat, graphs, #P-complete, D P -complete, NP-complete AMS subject classifications. 68Q15, 68R10. 1. Introduction. A number of papers in the literature [1, 5, 20, 21, 25] , etc., have considered the complexity of counting problems, proving many such problems to be # P-complete. Other papers have studied the complexity of Ambiguous and Unique satisfiability problems [23, 27] , proving such problems to be NP-hard and D Phard 1 respectively. Still other papers [3, 4, 5, 6, 15] have considered the complexity of decision problems when restricted to planar instances, proving many such problems to be NP-hard. In this paper, we combine these lines of research and prove for the first time that even when restricted to planar instances, many counting problems remain #P-complete, many ambiguous satisfiability problems remain NP-complete and many unique satisfiability problems remain D P -hard. 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. Such results are presented for several satisfiability, graph and combinatorial problems. These results show that planar counting, planar ambiguous satisfiability and planar unique satisfiability problems are as hard as arbitrary such problems, with
More recently, Hunt et al. proved the #P-hardness of many graph counting problems when restricted to planar instances REF .
The Complexity of Planar Counting Problems
ArXiv
ArXiv
Computer Science Mathematics