{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T21:09:33Z","timestamp":1705093773866},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2012,7,10]],"date-time":"2012-07-10T00:00:00Z","timestamp":1341878400000},"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>We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS).<\/jats:p><jats:p>We analyse the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result: for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial.<\/jats:p>","DOI":"10.1017\/s0963548312000296","type":"journal-article","created":{"date-parts":[[2012,7,10]],"date-time":"2012-07-10T14:49:46Z","timestamp":1341931786000},"page":"695-714","source":"Crossref","is-referenced-by-count":6,"title":["A Graph Polynomial for Independent Sets of Bipartite Graphs"],"prefix":"10.1017","volume":"21","author":[{"given":"Q.","family":"GE","sequence":"first","affiliation":[]},{"given":"D.","family":"\u0160TEFANKOVI\u010c","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,7,10]]},"reference":[{"key":"S0963548312000296_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"S0963548312000296_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_35"},{"key":"S0963548312000296_ref3","volume-title":"Exactly Solved Models in Statistical Mechanics","author":"Baxter","year":"1989"},{"key":"S0963548312000296_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"},{"key":"S0963548312000296_ref16","unstructured":"[16] Ge Q. and \u0160tefankovi\u010d D. (2010) A graph polynomial for independent sets of bipartite graphs. In FSTTCS, pp. 240\u2013250."},{"key":"S0963548312000296_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100023173"},{"key":"S0963548312000296_ref28","doi-asserted-by":"crossref","unstructured":"[28] Sly A. (2010) Computational transition at the uniqueness threshold. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287\u2013296.","DOI":"10.1109\/FOCS.2010.34"},{"key":"S0963548312000296_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0035-6"},{"key":"S0963548312000296_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511752506"},{"key":"S0963548312000296_ref31","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-010-9"},{"key":"S0963548312000296_ref26","doi-asserted-by":"publisher","DOI":"10.5802\/jtnb.318"},{"key":"S0963548312000296_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"S0963548312000296_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4789-6_9"},{"key":"S0963548312000296_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"S0963548312000296_ref29","unstructured":"[29] Stevenhagen P. (2000) Prime densities for second order torsion sequences. Preprint."},{"key":"S0963548312000296_ref18","unstructured":"[18] Goldberg L. A. and Jerrum M. R. (2010) Personal communication."},{"key":"S0963548312000296_ref25","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.2000.2547"},{"key":"S0963548312000296_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00221-3"},{"key":"S0963548312000296_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"S0963548312000296_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9022-9"},{"key":"S0963548312000296_ref32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321602"},{"key":"S0963548312000296_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9439-4"},{"key":"S0963548312000296_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"S0963548312000296_ref4","first-page":"97","volume-title":"STACS","author":"Bl\u00e4ser","year":"2008"},{"key":"S0963548312000296_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.08.003"},{"key":"S0963548312000296_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"S0963548312000296_ref7","doi-asserted-by":"crossref","first-page":"#R69","DOI":"10.37236\/793","article-title":"A multivariate interlace polynomial and its computation for graphs of bounded clique-width","volume":"15","author":"Courcelle","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548312000296_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4789-6_10"},{"key":"S0963548312000296_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"S0963548312000296_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<229::AID-RSA3>3.0.CO;2-X"},{"key":"S0963548312000296_ref2","volume-title":"Algorithmic Number Theory","author":"Bach","year":"1996"},{"key":"S0963548312000296_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"S0963548312000296_ref12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1071"},{"key":"S0963548312000296_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"S0963548312000296_ref6","doi-asserted-by":"crossref","unstructured":"[6] Bordewich M. and Kang R. J. (2011) Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width. In ICALP (1), pp. 533\u2013544.","DOI":"10.1007\/978-3-642-22006-7_45"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,10]],"date-time":"2020-07-10T14:23:22Z","timestamp":1594391002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000296\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,10]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["S0963548312000296"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000296","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,10]]}}}