Computer Science – Computational Complexity
Scientific paper
1998-09-11
Computer Science
Computational Complexity
25 pages, 12 figures, appears in SIAM J. Computing
Scientific paper
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.
Hunt III Harry B.
Marathe Madhav V.
Radhakrishnan Venkatesh
Stearns Richard E.
No associations
LandOfFree
The Complexity of Planar Counting Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Planar Counting Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Planar Counting Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-718930