{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:04:59Z","timestamp":1787508299427,"version":"build-2736575974"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,5,25]],"date-time":"2016-05-25T00:00:00Z","timestamp":1464134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"<jats:p>\n                    We study the problem \u2295H\n                    <jats:sc>oms<\/jats:sc>\n                    T\n                    <jats:sc>o<\/jats:sc>\n                    <jats:italic>H<\/jats:italic>\n                    of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph\n                    <jats:italic>H<\/jats:italic>\n                    . A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any\n                    <jats:italic>H<\/jats:italic>\n                    that contains no 4-cycles, \u2295H\n                    <jats:sc>oms<\/jats:sc>\n                    T\n                    <jats:sc>o<\/jats:sc>\n                    <jats:italic>H<\/jats:italic>\n                    is either in polynomial time or is \u2295P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.\n                  <\/jats:p>","DOI":"10.1145\/2898441","type":"journal-article","created":{"date-parts":[[2016,5,25]],"date-time":"2016-05-25T14:07:06Z","timestamp":1464185226000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Counting Homomorphisms to Square-Free Graphs, Modulo 2"],"prefix":"10.1145","volume":"8","author":[{"given":"Andreas","family":"G\u00f6bel","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Richerby","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25870-1_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"M. A. Armstrong. 1988. Groups and Symmetry. Springer-Verlag New York NY.  M. A. Armstrong. 1988. Groups and Symmetry. Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4757-4034-9"},{"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","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.08.003"},{"key":"e_1_2_1_6_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_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635825"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_1_10_1","article-title":"Approximately counting locally-optimal structures","author":"Goldberg L. A.","year":"2014","journal-title":"Journal of Computer and System Sciences."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/11523.11527"},{"key":"e_1_2_1_12_1","volume-title":"28th International Symposium on Theoretical Aspects of Computer Science (STACS\u201911)","volume":"9","author":"Guo H."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press New York NY.  P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press New York NY.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 6th GI-Conference on Theoretical Computer Science. Springer-Verlag, 269--275","author":"Papadimitriou C. H."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898441","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898441","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:56:30Z","timestamp":1750208190000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898441"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,25]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2898441"],"URL":"https:\/\/doi.org\/10.1145\/2898441","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,25]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}