{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T10:27:28Z","timestamp":1657621648802},"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":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"\n We study the problem \u2295H\n oms<\/jats:sc>\n T\n o<\/jats:sc>\n H<\/jats:italic>\n of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph\n 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 H<\/jats:italic>\n that contains no 4-cycles, \u2295H\n oms<\/jats:sc>\n T\n o<\/jats:sc>\n 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-25T18:07:06Z","timestamp":1464199626000},"page":"1-29","source":"Crossref","is-referenced-by-count":4,"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"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"David","family":"Richerby","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]}],"member":"320","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\/pdf\/10.1145\/2898441","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T20:04:00Z","timestamp":1614629040000},"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":"http:\/\/dx.doi.org\/10.1145\/2898441","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":["Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[2016,5,25]]}}}