{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:32:19Z","timestamp":1787502739892,"version":"build-2736575974"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"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":["EP\/1011528\/1"],"award-info":[{"award-number":["EP\/1011528\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n                    A homomorphism from a graph\n                    <jats:italic>G<\/jats:italic>\n                    to a graph\n                    <jats:italic>H<\/jats:italic>\n                    is a function from\n                    <jats:italic>V<\/jats:italic>\n                    (\n                    <jats:italic>G<\/jats:italic>\n                    ) to\n                    <jats:italic>V<\/jats:italic>\n                    (\n                    <jats:italic>H<\/jats:italic>\n                    ) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph\n                    <jats:italic>H<\/jats:italic>\n                    has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs\n                    <jats:italic>H<\/jats:italic>\n                    , counting homomorphisms to\n                    <jats:italic>H<\/jats:italic>\n                    modulo 2 can be done in polynomial time. For every other fixed cactus graph\n                    <jats:italic>H<\/jats:italic>\n                    , the problem is complete in the complexity class \u2295\n                    <jats:italic>P<\/jats:italic>\n                    , which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which\n                    <jats:italic>H<\/jats:italic>\n                    lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which\n                    <jats:italic>H<\/jats:italic>\n                    is a tree.\n                  <\/jats:p>","DOI":"10.1145\/2635825","type":"journal-article","created":{"date-parts":[[2014,8,21]],"date-time":"2014-08-21T08:19:12Z","timestamp":1408609152000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The complexity of counting homomorphisms to cactus graphs modulo 2"],"prefix":"10.1145","volume":"6","author":[{"given":"Andreas","family":"G\u00f6bel","sequence":"first","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Richerby","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.033"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00255"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of ICALP (1). 275--286","author":"Cai J.-Y.","unstructured":"Cai , J.-Y. , Chen , X. , and Lu , P . 2010. Graph homomorphisms with complex values: a dichotomy theorem . In Proceedings of ICALP (1). 275--286 . Cai, J.-Y., Chen, X., and Lu, P. 2010. Graph homomorphisms with complex values: a dichotomy theorem. In Proceedings of ICALP (1). 275--286."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070690201"},{"key":"e_1_2_1_7_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_8_1","unstructured":"Faben J. 2008. The complexity of counting solutions to generalised satisfiability problems modulo k. CoRR abs\/0809.1836.  Faben J. 2008. The complexity of counting solutions to generalised satisfiability problems modulo k . CoRR abs\/0809.1836 ."},{"key":"e_1_2_1_10_1","unstructured":"Faben J. and Jerrum M. 2013. The complexity of parity graph homomorphism: an initial investigation. CoRR abs\/1309.4033.  Faben J. and Jerrum M. 2013. The complexity of parity graph homomorphism: an initial investigation. CoRR abs\/1309.4033 ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/11523.11527"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of STACS. 249--260","author":"Guo H.","unstructured":"Guo , H. , Huang , S. , Lu , P. , and Xia , M . 2011. The complexity of weighted Boolean &num;CSP modulo k . In Proceedings of STACS. 249--260 . Guo, H., Huang, S., Lu, P., and Xia, M. 2011. The complexity of weighted Boolean &num;CSP modulo k. In Proceedings of STACS. 249--260."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/100815530"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.4.315"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"119","DOI":"10.2307\/2310010","article-title":"Another proof of Cauchy\u2019s group theorem","volume":"66","author":"McKay J. H.","year":"1959","unstructured":"McKay , J. H. 1959 . Another proof of Cauchy\u2019s group theorem . Amer. Math. Monthly 66 , 119 . McKay, J. H. 1959. Another proof of Cauchy\u2019s group theorem. Amer. Math. Monthly 66, 119.","journal-title":"Amer. Math. Monthly"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 6th GI-Conference on Theoretical Computer Science. Springer-Verlag, 269--276","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. and Zachos , S . 1982. Two remarks on the power of counting . In Proceedings of the 6th GI-Conference on Theoretical Computer Science. Springer-Verlag, 269--276 . Papadimitriou, C. H. and Zachos, S. 1982. Two remarks on the power of counting. In Proceedings of the 6th GI-Conference on Theoretical Computer Science. Springer-Verlag, 269--276."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2010.0252"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.7"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635825","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2635825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:03:44Z","timestamp":1750259024000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2635825"],"URL":"https:\/\/doi.org\/10.1145\/2635825","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}