{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T12:38:48Z","timestamp":1788871128686,"version":"build-2803163510"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["334828"],"award-info":[{"award-number":["334828"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/I011935\/1 Computational Counting"],"award-info":[{"award-number":["EP\/I011935\/1 Computational Counting"]}],"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. Comput. Theory"],"published-print":{"date-parts":[[2014,5]]},"abstract":"\n We study two computational problems, parameterised by a fixed tree\n H<\/jats:italic>\n . #HOMSTO(\n H<\/jats:italic>\n ) is the problem of counting homomorphisms from an input graph\n G<\/jats:italic>\n to\n H<\/jats:italic>\n . #WHOMSTO(\n H<\/jats:italic>\n ) is the problem of counting weighted homomorphisms to\n H<\/jats:italic>\n , given an input graph\n G<\/jats:italic>\n and a weight function for each vertex\n v<\/jats:italic>\n of\n G<\/jats:italic>\n . Even though\n H<\/jats:italic>\n is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #\n P<\/jats:italic>\n . We give a complete trichotomy for #WHOMSTO(\n H<\/jats:italic>\n ). If\n H<\/jats:italic>\n is a star, then #WHOMSTO(\n H<\/jats:italic>\n ) is in FP. If\n H<\/jats:italic>\n is not a star but it does not contain a certain induced subgraph\n J<\/jats:italic>\n 3, then #WHOMSTO(\n H<\/jats:italic>\n ) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RH\u03a01 under AP-reductions. Finally, if\n H<\/jats:italic>\n contains an induced\n J<\/jats:italic>\n 3<\/jats:sub>\n , then #WHOMSTO(\n H<\/jats:italic>\n ) is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHOMSTO(\n H<\/jats:italic>\n ) is complete for #P under AP-reductions. The results are similar for #HOMSTO(\n H<\/jats:italic>\n ) except that a rich structure emerges if\n H<\/jats:italic>\n contains an induced\n J<\/jats:italic>\n 3<\/jats:sub>\n . We show that there are trees\n H<\/jats:italic>\n for which #HOMSTO(\n H<\/jats:italic>\n ) is #\n SAT<\/jats:italic>\n -equivalent (disproving a plausible conjecture of Kelk). However, it is still not known whether #HOMSTO(\n H<\/jats:italic>\n ) is #SAT-hard for every tree\n H<\/jats:italic>\n which contains an induced\n J<\/jats:italic>\n 3. It turns out that there is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the\n ferromagnetic Potts model<\/jats:italic>\n . In particular, we show that for a family of graphs\n Jq<\/jats:italic>\n , parameterised by a positive integer\n q<\/jats:italic>\n , the problem #HOMSTO(\n Jq<\/jats:italic>\n ) is AP-interreducible with the problem of approximating the partition function of the\n q<\/jats:italic>\n -state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HOMSTO(\n Jq<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/2600917","type":"journal-article","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T08:50:17Z","timestamp":1402390217000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Approximately Counting Tree Homomorphisms"],"prefix":"10.1145","volume":"6","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"Queen Mary, University of London"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"17","article-title":"On sampling colorings of bipartite graphs","volume":"8","author":"Balasubramanian R.","year":"2006","unstructured":"R. Balasubramanian and C. R. Subramanian . 2006 . On sampling colorings of bipartite graphs . Disc. Math. Theor. Comput. Sci. 8 , 1, 17 -- 30 (electronic). R. Balasubramanian and C. R. Subramanian. 2006. On sampling colorings of bipartite graphs. Disc. Math. Theor. Comput. Sci. 8, 1, 17--30 (electronic).","journal-title":"Disc. Math. Theor. Comput. Sci."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00189-P"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_2_1_4_1","volume-title":"Graphs, Morphisms and Statistical Physics, DIMACS Services in Discrete Mathematics and Theoretical Computer Science","author":"Borgs Christian","unstructured":"Christian Borgs , Jennifer T. Chayes , Martin Dyer , and Prasad Tetali . 2004. On the sampling problem for H-colorings on the hypercubic lattice . In Graphs, Morphisms and Statistical Physics, DIMACS Services in Discrete Mathematics and Theoretical Computer Science , vol. 63 . American Mathematical Society , Providence, RI , 13--28. Christian Borgs, Jennifer T. Chayes, Martin Dyer, and Prasad Tetali. 2004. On the sampling problem for H-colorings on the hypercubic lattice. In Graphs, Morphisms and Statistical Physics, DIMACS Services in Discrete Mathematics and Theoretical Computer Science, vol. 63. American Mathematical Society, Providence, RI, 13--28."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528401"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1142"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/791230.792302"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.08.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4%3C260::AID-RSA5%3E3.0.CO;2-W"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408363"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90294-K"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_21_1","volume-title":"Oxford Lecture Series in Mathematics and its Applications","author":"Hell Pavol","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il . 2004. Graphs and Homomorphisms . Oxford Lecture Series in Mathematics and its Applications , Vol. 28 , Oxford University Press , Oxford, UK . DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001. 10.1093\/acprof:oso Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications, Vol. 28, Oxford University Press, Oxford, UK. DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)00099-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100027419"},{"key":"e_1_2_1_30_1","volume-title":"Surveys in Combinatorics","author":"Sokal Alan","unstructured":"Alan Sokal . 2005. The multivariate Tutte polynomial . In Surveys in Combinatorics , Cambridge University Press , 173--226. Alan Sokal. 2005. The multivariate Tutte polynomial. In Surveys in Combinatorics, Cambridge University Press, 173--226."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2600917","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2600917","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:55:53Z","timestamp":1750215353000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2600917"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2600917"],"URL":"https:\/\/doi.org\/10.1145\/2600917","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}