{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:06Z","timestamp":1750220466699,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"\n Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of\u00a0 #\n \n p<\/jats:italic>\n <\/jats:sub>\n H\n OMS<\/jats:sc>\n T\n O<\/jats:sc>\n H<\/jats:italic>\n , the problem of counting graph homomorphisms from an input graph to a graph\n H<\/jats:italic>\n modulo a prime number\u00a0\n p<\/jats:italic>\n . Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo\u00a02, however, the influence of the structure of\u00a0\n H<\/jats:italic>\n on the tractability was shown to persist, which yields similar dichotomies.\n <\/jats:p>\n \n Our main result states that for every tree\u00a0\n H<\/jats:italic>\n and every prime\u00a0\n p<\/jats:italic>\n the problem #\n \n p<\/jats:italic>\n <\/jats:sub>\n H\n OMS<\/jats:sc>\n T\n O<\/jats:sc>\n H<\/jats:italic>\n is either polynomial time computable or #\n \n p<\/jats:italic>\n <\/jats:sub>\n P-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph\n H<\/jats:italic>\n when counting modulo\u00a02. In contrast to previous results on modular counting, the tractable cases of #\n \n p<\/jats:italic>\n <\/jats:sub>\n H\n OMS<\/jats:sc>\n T\n O<\/jats:sc>\n H<\/jats:italic>\n are essentially the same for all values of the modulo when\n H<\/jats:italic>\n is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime\u00a0\n p<\/jats:italic>\n . These results are the first suggesting that such dichotomies hold not only for the modulo\u00a02 case but also for the modular counting functions of all primes\u00a0\n p<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3460958","type":"journal-article","created":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T17:35:03Z","timestamp":1640280903000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Homomorphisms to Trees Modulo a Prime"],"prefix":"10.1145","volume":"13","author":[{"given":"Andreas","family":"G\u00f6bel","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}]},{"given":"J. A. Gregor","family":"Lagodzinski","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}]},{"given":"Karen","family":"Seidel","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"M. A. Armstrong. 1988. Groups and Symmetry. Springer-Verlag. M. A. Armstrong. 1988. Groups and Symmetry. Springer-Verlag.","DOI":"10.1007\/978-1-4757-4034-9"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110840194"},{"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","unstructured":"D. S. Dummit and R. M. Foote. 1991. Abstract Algebra. Prentice Hall. 90035456 D. S. Dummit and R. M. Foote. 1991. Abstract Algebra. Prentice Hall. 90035456"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/360708.360731"},{"key":"e_1_2_1_8_1","unstructured":"J. Faben. 2008. The complexity of counting solutions to generalised satisfiability problems modulo k. arxiv:0809.1836. Retrieved from https:\/\/arxiv.org\/abs\/0809.1836. J. Faben. 2008. The complexity of counting solutions to generalised satisfiability problems modulo k. arxiv:0809.1836. Retrieved from https:\/\/arxiv.org\/abs\/0809.1836."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3458064.3458201"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635825"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898441"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/11523.11527"},{"volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201911)","author":"Guo H.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"volume-title":"Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919)","year":"2019","author":"Kazeminia A.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201921)","author":"Lagodzinski J. A. G.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647211.720053"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.7"},{"edition":"2","volume-title":"Introduction to Graph Theory","author":"West D. B.","key":"e_1_2_1_27_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460958","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:22Z","timestamp":1750193302000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3460958"],"URL":"https:\/\/doi.org\/10.1145\/3460958","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,9,30]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}