The Complexity of Planar Counting Problems

Simple item page
dc.creatorHunt III, Harry B.
dc.creatorMarathe, Madhav V.
dc.creatorRadhakrishnan, Venkatesh
dc.creatorStearns, Richard E.
dc.date1998-09-11
dc.date.accessioned2026-07-07T06:32:47Z
dc.date.available2026-07-07T06:32:47Z
dc.descriptionWe 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 $ε$-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.
dc.description25 pages, 12 figures, appears in SIAM J. Computing
dc.identifierhttps://arxiv.org/abs/cs/9809017
dc.identifierhttp://arxiv.org/abs/cs/9809017
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/98978
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectF.1.3
dc.titleThe Complexity of Planar Counting Problems
dc.typetext

Files

Collections

arXiv