{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:26Z","timestamp":1787321126485,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["714532"],"award-info":[{"award-number":["714532"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M508111\/1"],"award-info":[{"award-number":["EP\/M508111\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [ Theory Comput., 11 (2015), pp. 35--57] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class $\\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\\oplus{P}$-complete cases, assuming the randomized exponential time hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph $H$. Using this, we subsume all prior progress toward resolving the conjecture (Faben and Jerrum [ Theory Comput., 11 (2015), pp. 35--57]; G\u00f6bel, Goldberg, and Richerby [ ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2.<\/jats:p>","DOI":"10.1137\/20m1382921","type":"journal-article","created":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T10:25:48Z","timestamp":1637231148000},"page":"2749-2814","source":"Crossref","is-referenced-by-count":1,"title":["Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":true,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Roth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,18]]},"reference":[{"key":"atypb1","first-page":"315","author":"Borgs C.","year":"2006","journal-title":"Berlin"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1899"},{"key":"atypb3","first-page":"364","author":"Chen H.","year":"2019","journal-title":"Berlin"},{"key":"atypb4","first-page":"210","author":"Curticapean R.","year":"2017","journal-title":"ACM"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2635812"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00017-8"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 5th ed., Grad. Texts in Math. 173, Springer, Berlin, 2016.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"atypb11","unstructured":"J. Faben,\n                      The Complexity of Counting Solutions to Generalised Satisfiability Problems Modulo k\n                      , preprint,arXiv:0809.1836, 2008."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a002"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/3458040"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020551"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/3037381"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2635825"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2898441"},{"key":"atypb20","unstructured":"A. G\u00f6bel, J. A. G. Lagodzinski, and K. Seidel,\n                      Counting homomorphisms to trees modulo a prime\n                      , in 43rd International Symposium on Mathematical Foundations of Computer Science, I. Potapov, P. G. Spirakis, and J. Worrell, eds., LIPIcs Leibniz Int. Proc. Inform. 117, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2018, 49,https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.49."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/2600917"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90165-9"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"atypb25","first-page":"657","author":"Grohe M.","year":"2001","journal-title":"ACM"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb28","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"atypb29","unstructured":"A. Kazeminia and A. A. Bulatov,\n                      Counting homomorphisms modulo a prime number\n                      , in 44th International Symposium on Mathematical Foundations of Computer Science, Aachen, Germany, P. Rossmanith, P. Heggernes, and J. Katoen, eds., LIPIcs Leibniz Int. Proc. Inform. 138, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2019, 59,https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.59."},{"key":"atypb30","unstructured":"S. Kelk,\n                      On the Relative Complexity of Approximately Counting $H$-Colourings\n                      , Ph.D. thesis, Warwick University, 2003."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"atypb32","first-page":"75","volume":"43","author":"Lov\u00e1sz L.","year":"2006","journal-title":"S.)"},{"key":"atypb33","first-page":"269","author":"Papadimitriou C. H.","year":"1982","journal-title":"Berlin"},{"key":"atypb34","first-page":"2161","author":"Roth M.","year":"2020","journal-title":"Philadelphia"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"atypb36","first-page":"509","author":"Valiant L. G.","year":"2006","journal-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1382921","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:50Z","timestamp":1787317610000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1382921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1382921"],"URL":"https:\/\/doi.org\/10.1137\/20m1382921","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}