{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:29Z","timestamp":1759063409270,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["GR\/S26323\/01"],"award-info":[{"award-number":["GR\/S26323\/01"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, PCSP has scores that are arbitrary multivariate formal polynomials, or indeed take values in an arbitrary ring.<\/jats:p>\n          <jats:p>Although PCSP is much more general than CSP, remarkably, all (exact, exponential-time) algorithms we know of for 2-CSP (where each score depends on at most 2 variables) extend to 2-PCSP, at the expense of just a polynomial factor in running time. Specifically, we extend the reduction-based algorithm of Scott and Sorkin [2007]; the specialization of that approach to sparse random instances, where the algorithm runs in polynomial expected time; dynamic-programming algorithms based on tree decompositions; and the split-and-list matrix-multiplication algorithm of Williams [2004].<\/jats:p>\n          <jats:p>This gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a maximum bisection of a graph, and calculating the partition function of an Ising model. It also yields the most efficient algorithm known for certain instances of counting and\/or weighted Maximum Independent Set. Furthermore, PCSP solves both optimization and counting versions of a wide range of problems, including all CSPs, and thus enables samplers including uniform sampling of optimal solutions and Gibbs sampling of all solutions.<\/jats:p>","DOI":"10.1145\/1597036.1597049","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function"],"prefix":"10.1145","volume":"5","author":[{"given":"Alexander D.","family":"Scott","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"2","article-title":"Discrete","volume":"54","author":"Arnborg S.","year":"1994","journal-title":"Appl. Math."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.41"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119186"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.40"},{"volume-title":"SIAM J. Comput. (Special Issue FOCS","year":"2006","author":"Bj\u00f6rklund A.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970002"},{"volume":"5018","volume-title":"Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC'08)","author":"Bourgeois N.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.037"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90002-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_5"},{"volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06)","author":"Fomin F. V.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1138831.1711171"},{"key":"e_1_2_1_19_1","unstructured":"F\u00fcrer M. and Kasiviswanathan S. P. 2005. Algorithms for counting 2-SAT solutions and colorings with applications. Tech. rep. 33 Electronic Colloquium on Computational Complexity.  F\u00fcrer M. and Kasiviswanathan S. P. 2005. Algorithms for counting 2-SAT solutions and colorings with applications. Tech. rep. 33 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_20_1","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications vol. 28. Oxford University Press Oxford UK.  Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications vol. 28. Oxford University Press Oxford UK."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970139567X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/080715482"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1139168.1139173"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Mathematical Foundations of Computer Science","volume":"2136","author":"Monien B.","year":"2001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129734"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"volume-title":"Surveys in Combinatorics","year":"2005","author":"Scott A. D.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","unstructured":"Scott A. D. and Sorkin G. B. 2006a. Generalized constraint satisfaction problems. Tech. rep. cs:DM\/0604079v1 arxiv.org. Apr. http:\/\/arxiv.org\/abs\/cs.DM\/0604079.  Scott A. D. and Sorkin G. B. 2006a. Generalized constraint satisfaction problems. Tech. rep. cs:DM\/0604079v1 arxiv.org. Apr. http:\/\/arxiv.org\/abs\/cs.DM\/0604079."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830500725X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.08.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789712"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_101"},{"key":"e_1_2_1_34_1","unstructured":"Williams R. 2008. Finding paths of length k in O&ast;(2<sup>k<\/sup>) time. Tech. rep. cs.DS\/0807.3026v3 arxiv.org. November. http:\/\/arxiv.org\/abs\/cs.DM\/0604080.  Williams R. 2008. Finding paths of length k in O&ast;(2<sup>k<\/sup>) time. Tech. rep. cs.DS\/0807.3026v3 arxiv.org. November. http:\/\/arxiv.org\/abs\/cs.DM\/0604080."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1597036.1597049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:11Z","timestamp":1750249091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1597036.1597049"],"URL":"https:\/\/doi.org\/10.1145\/1597036.1597049","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2006-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}