{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:50Z","timestamp":1787337470133,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    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 [J. B. Saxe, Two Papers on Graph Embedding Problems, Tech. Report CMU-CS-80-102, Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 1980] and the D\n                    <jats:sup>P<\/jats:sup>\n                    -completeness (with respect to random polynomial reducibility) of the unique satisfiability problems [L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions, in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 458--463] associated with several of the above problems, when restricted to planar instances. Previously, very few #P}-hardness results, no {\\sf NP}-hardness results, and no D\n                    <jats:sup>P<\/jats:sup>\n                    -completeness results were known for counting problems, ambiguous satisfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances.\n                  <\/jats:p>\n                  <jats:p>Assuming {\\sf P \\neq $ NP}, one corollary of the above results is that 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.<\/jats:p>","DOI":"10.1137\/s0097539793304601","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1142-1167","source":"Crossref","is-referenced-by-count":69,"title":["The Complexity of Planar Counting Problems"],"prefix":"10.1137","volume":"27","author":[{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"G. Brightwell and P. Winkler,\n                      Counting linear extensions is #P\u2010complete\n                      , in Proc. 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 175\u2013181."},{"key":"R2","unstructured":"A.Bertoni, G.Mauri, and N.Sabadini,\n                      A characterization of the class of functions computable in polynomial time on Random Access Machines\n                      , in Proc. 13th Annual ACM Symposium on Theory of Computing, pp.168\u2010176, 1981."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90002-7"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90008-3"},{"key":"R6","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"R9","unstructured":"H. B. Hunt III, R. E. Stearns, and M. V. Marathe,\n                      Local Reductions, Generalized Satisfiability, Complexity and Efficient Approximability\n                      : I, in preparation. A preliminary version of the paper appears in Proc. 9th ACM Conference on Structure in Complexity Theory, 1994, pp. 356\u2013366."},{"key":"R10","unstructured":"H. B. Hunt III, R. E. Stearns, and M. V. Marathe,\n                      Local Reductions, Generalized Satisfiability, Complexity and Efficient Approximability\n                      : II, in preparation. A preliminary version of the paper appears in Proc. 9th ACM Conf. on Structure in Complexity Theory, 1994, pp. 356\u2013366."},{"key":"R11","unstructured":"H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns,\n                      Parallel approximation schemes for planar and near\u2010planar satisfiability and graph problems\n                      , Inform. and Comput., submitted, 1998."},{"key":"R11","unstructured":"A preliminary version appears in Proc. 14th Foundations of Software Technology and Theoretical Computer Science (FST & TCS), Lecture Notes in Comp. Sci. 761, Springer\u2010Verlag, New York, 1994, pp. 342\u2013353. A complete version of the paper appears as Technical Report No. LA\u2010UR\u201096\u20102723, Los Alamos National Laboratory, Los Alamos, NM, 1996."},{"key":"R12","unstructured":"H. B. Hunt III, V. Radhakrishnan, M. V. Marathe, and R. E. Stearns,\n                      On the Complexity of Planar Graph\/Hypergraph Coloring\n                      , in preparation, 1997."},{"key":"R13","first-page":"317","volume":"1","author":"Kann V.","year":"1994","journal-title":"Nordic J. Comput."},{"key":"R14","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85\u2013103."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(85)90021-4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0218073"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0607036"},{"key":"R19","unstructured":"M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan,\n                      Complexity of Hierarchically and 1\u2010Dimensional Periodically Specified Problems\n                      , Technical Report No. LA\u2010UR\u201095\u20103348, Los Alamos National Laboratory, Los Alamos, NM, August 1995."},{"key":"R19","unstructured":"Also presented at the\n                      DIMACS Workshop on Satisfiability Problem: Theory and Applications\n                      , March 1996."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"R21","unstructured":"C. Papadimitriou,\n                      Computational Complexity\n                      , Addison\u2010Wesley, Reading, MA, 1994."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0215050"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1039"},{"key":"R25","unstructured":"J. B. Saxe,\n                      Two Papers on Graph Embedding Problems\n                      , Technical Report CMU\u2010CS\u201080\u2010102, Dept. of Comp. Science, Carnegie Mellon University, 1980."},{"key":"R26","unstructured":"Thomas Schaefer, The complexity of satisfiability problems, ACM, New York, 1978, 216\u201322680d:68058"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"R29","unstructured":"L. G. Valiant and V. V. Vazirani,\n                      NP is as easy as detecting unique solutions\n                      , in Proc. 17th Annual ACM Symp. on Theory of Computing, 1985, pp. 458\u2013463."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"},{"key":"R31","unstructured":"S. Vadhan,\n                      The Complexity of Counting in Sparse, Regular and Planar Graphs\n                      , Technical Report, MIT, Cambridge, MA, 1997."},{"key":"R31","unstructured":"Also available online from www\u2010math.mit.edu\/\u223csalil."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793304601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:09Z","timestamp":1787335929000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793304601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793304601"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793304601","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}