{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T08:09:35Z","timestamp":1672992575594},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2012,7,4]],"date-time":"2012-07-04T00:00:00Z","timestamp":1341360000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest is that of the Ising model with constant energies and external field. One may consider such an Ising system as a simple graph together with vertex and edge weights. When these weights are considered indeterminates, the partition function for the constant case is a trivariate polynomial<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;x,y,z). This polynomial was studied with respect to its approximability by Goldberg, Jerrum and Paterson.<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;x,y,z) generalizes a bivariate polynomial<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;t,y), which was studied in by Andr\u00e9n and Markstr\u00f6m.<\/jats:p><jats:p>We consider the complexity of<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>t,y) and<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;x,y,z) in comparison to that of the Tutte polynomial, which is well known to be closely related to the Potts model in the absence of an external field. We show that<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;x,y,z) is #<jats:bold>P<\/jats:bold>-hard to evaluate at all points in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000259_char1\" \/><\/jats:private-char><jats:sup>3<\/jats:sup>, except those in an exceptional set of low dimension, even when restricted to simple graphs which are bipartite and planar. A counting version of the Exponential Time Hypothesis, #<jats:bold>ETH<\/jats:bold>, was introduced by Dell, Husfeldt and Wahl\u00e9n in order to study the complexity of the Tutte polynomial. In analogy to their results, we give under #<jats:bold>ETH<\/jats:bold>a dichotomy theorem stating that evaluations of<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;t,y) either take exponential time in the number of vertices of<jats:italic>G<\/jats:italic>to compute, or can be done in polynomial time. Finally, we give an algorithm for computing<jats:italic>Z<\/jats:italic>(<jats:italic>G<\/jats:italic>;x,y,z) in polynomial time on graphs of bounded clique-width, which is not known in the case of the Tutte polynomial.<\/jats:p>","DOI":"10.1017\/s0963548312000259","type":"journal-article","created":{"date-parts":[[2012,7,5]],"date-time":"2012-07-05T03:53:13Z","timestamp":1341460393000},"page":"743-772","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Ising Polynomials"],"prefix":"10.1017","volume":"21","author":[{"given":"TOMER","family":"KOTEK","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,7,4]]},"reference":[{"key":"S0963548312000259_ref27","unstructured":"[27] Thurley M. The Complexity of Partition Functions. PhD thesis, Humboldt Universit\u00e4t zu Berlin."},{"key":"S0963548312000259_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"S0963548312000259_ref11","first-page":"493","volume-title":"SODA","author":"Fomin","year":"2010"},{"key":"S0963548312000259_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.04.012"},{"key":"S0963548312000259_ref23","first-page":"49","volume-title":"WG 2005","author":"Oum","year":"2005"},{"key":"S0963548312000259_ref29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446797"},{"key":"S0963548312000259_ref25","first-page":"941","volume-title":"SODA","author":"Sinclair","year":"2011"},{"key":"S0963548312000259_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.021"},{"key":"S0963548312000259_ref22","doi-asserted-by":"crossref","first-page":"R64","DOI":"10.37236\/153","article-title":"Evaluating a weighted graph polynomial for graphs of bounded tree-width","volume":"16","author":"Noble","year":"2009","journal-title":"Electron. J. Combin."},{"key":"S0963548312000259_ref20","first-page":"191","volume-title":"WG 2006","author":"Makowsky","year":"2006"},{"key":"S0963548312000259_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"S0963548312000259_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"S0963548312000259_ref15","volume-title":"Concrete Mathematics","author":"Graham","year":"1994"},{"key":"S0963548312000259_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"S0963548312000259_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/050645208"},{"key":"S0963548312000259_ref8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","article-title":"On the computational complexity of the Jones and Tutte polynomials","volume":"108","author":"Vertigan","year":"1990","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"S0963548312000259_ref18","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"Kasteleyn","year":"1967"},{"key":"S0963548312000259_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548312000259_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"S0963548312000259_ref6","first-page":"426","volume-title":"ICALP 1","author":"Dell","year":"2010"},{"key":"S0963548312000259_ref26","first-page":"173","volume-title":"Surveys in Combinatorics","author":"Sokal","year":"2005"},{"key":"S0963548312000259_ref16","first-page":"237","volume-title":"Proc. 14th Annual IEEE Conference on Computational Complexity: CCC-99","author":"Impagliazzo","year":"1999"},{"key":"S0963548312000259_ref4","first-page":"275","volume-title":"ICALP 1","author":"Cai","year":"2010"},{"key":"S0963548312000259_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"S0963548312000259_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"S0963548312000259_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00113-7"},{"key":"S0963548312000259_ref9","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704825"},{"key":"S0963548312000259_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"},{"key":"S0963548312000259_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"S0963548312000259_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342928"},{"key":"S0963548312000259_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000195"},{"key":"S0963548312000259_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003551"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,10]],"date-time":"2020-07-10T07:25:18Z","timestamp":1594365918000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000259\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,4]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["S0963548312000259"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000259","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,4]]}}}