{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:23:18Z","timestamp":1787509398059,"version":"build-2736575974"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/M508111\/1"],"award-info":[{"award-number":["EP\/M508111\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC","award":["334828"],"award-info":[{"award-number":["334828"]}]},{"name":"European Research Council under the European Union\u2019s Seventh Framework Programme","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n                    A\n                    <jats:italic>retraction<\/jats:italic>\n                    is a homomorphism from a graph\n                    <jats:italic>G<\/jats:italic>\n                    to an induced subgraph\n                    <jats:italic>H<\/jats:italic>\n                    of\n                    <jats:italic>G<\/jats:italic>\n                    that is the identity on\n                    <jats:italic>H<\/jats:italic>\n                    . In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length 4). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new #BIS-easiness results, we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs that were previously unresolved.\n                  <\/jats:p>","DOI":"10.1145\/3458040","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T01:26:33Z","timestamp":1626398793000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Approximately Counting Retractions to Square-free Graphs"],"prefix":"10.1145","volume":"17","author":[{"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"University of Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-010-9364-1"},{"key":"e_1_2_1_2_1","volume-title":"Wampler","author":"Arends Felix","year":"2011","unstructured":"Felix Arends , Jo\u00ebl Ouaknine , and Charles W . Wampler . 2011 . On searching for small Kochen-Specker vector systems. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer , 23\u201334. Felix Arends, Jo\u00ebl Ouaknine, and Charles W. Wampler. 2011. On searching for small Kochen-Specker vector systems. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 23\u201334."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90646-W"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.029"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90009-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00321-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-17-1-152-170"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_9_1","unstructured":"Ilkyoo Choi Daniel W. Cranston and Th\u00e9o Pierron. 2018. Degeneracy and colorings of squares of planar graphs without 4-cycles. Retrieved from https:\/\/arXiv:1806.07204.  Ilkyoo Choi Daniel W. Cranston and Th\u00e9o Pierron. 2018. Degeneracy and colorings of squares of planar graphs without 4-cycles. Retrieved from https:\/\/arXiv:1806.07204."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130107"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958204.1958205"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_20_1","first-page":"327","article-title":"Extremal graphs without 4-cycles. J. Combin. Theory","volume":"103","author":"Firke Frank A.","year":"2013","unstructured":"Frank A. Firke , Peter M. Kosek , Evan D. Nash , and Jason Williford . 2013 . Extremal graphs without 4-cycles. J. Combin. Theory , Ser. B 103 , 3 (2013), 327 \u2013 336 . Frank A. Firke, Peter M. Kosek, Evan D. Nash, and Jason Williford. 2013. Extremal graphs without 4-cycles. J. Combin. Theory, Ser. B 103, 3 (2013), 327\u2013336.","journal-title":"Ser. B"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397472"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90018-7"},{"key":"e_1_2_1_23_1","volume-title":"Erd\u0151s Centennial","author":"F\u00fcredi Zolt\u00e1n","unstructured":"Zolt\u00e1n F\u00fcredi and Mikl\u00f3s Simonovits . 2013. The history of degenerate (bipartite) extremal graph problems . In Erd\u0151s Centennial . Springer , 169\u2013264. Zolt\u00e1n F\u00fcredi and Mikl\u00f3s Simonovits. 2013. The history of degenerate (bipartite) extremal graph problems. In Erd\u0151s Centennial. Springer, 169\u2013264."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020551"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037381"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170511"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898441"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600917"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408363"},{"key":"e_1_2_1_32_1","volume-title":"Retractions des graphes. ProQuest LLC","author":"Hell Pavol","unstructured":"Pavol Hell . 1973. Retractions des graphes. ProQuest LLC , Ann Arbor, MI . Retrieved from DOI:http:\/\/ezproxy-prd.bodleian.ox.ac.uk:2175\/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi\/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:0289365. Pavol Hell. 1973. Retractions des graphes. ProQuest LLC, Ann Arbor, MI. Retrieved from DOI:http:\/\/ezproxy-prd.bodleian.ox.ac.uk:2175\/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi\/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:0289365."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066450"},{"key":"e_1_2_1_34_1","volume-title":"Oxford Lecture Series in Mathematics and its Applications","author":"Hell Pavol","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il . 2004. Graphs and Homomorphisms . Oxford Lecture Series in Mathematics and its Applications , Vol. 28 . Oxford University Press , Oxford . xii+244 pages. DOI:https:\/\/doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001 Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications, Vol. 28. Oxford University Press, Oxford. xii+244 pages. DOI:https:\/\/doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1987-025-1"},{"key":"e_1_2_1_37_1","first-page":"708","article-title":"Sudoku squares and chromatic polynomials","volume":"54","author":"Herzberg Agnes M.","year":"2007","unstructured":"Agnes M. Herzberg and M. Ram Murty . 2007 . Sudoku squares and chromatic polynomials . Notices Amer. Math. Soc. 54 , 6 (2007), 708 \u2013 717 . Agnes M. Herzberg and M. Ram Murty. 2007. Sudoku squares and chromatic polynomials. Notices Amer. Math. Soc. 54, 6 (2007), 708\u2013717.","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_38_1","volume-title":"Young","author":"Hocking John G.","year":"1961","unstructured":"John G. Hocking and Gail S . Young . 1961 . Topology. Addison-Wesley Publishing , Reading, MA\/London. ix+374 pages. John G. Hocking and Gail S. Young. 1961. Topology. Addison-Wesley Publishing, Reading, MA\/London. ix+374 pages."},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Precoloring extension. II. Graphs classes related to bipartite graphs","volume":"62","author":"Hujter M.","year":"1993","unstructured":"M. Hujter and Zs. Tuza . 1993 . Precoloring extension. II. Graphs classes related to bipartite graphs . Acta Math. Univ. Comenian. (N.S.) 62 , 1 (1993), 1 \u2013 11 . M. Hujter and Zs. Tuza. 1993. Precoloring extension. II. Graphs classes related to bipartite graphs. Acta Math. Univ. Comenian. (N.S.) 62, 1 (1993), 1\u201311.","journal-title":"Acta Math. Univ. Comenian. (N.S.)"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001826"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00085-6"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919)","volume":"138","author":"Kazeminia Amirhossein","year":"2019","unstructured":"Amirhossein Kazeminia and Andrei A. Bulatov . 2019. Counting homomorphisms modulo a prime number . In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919) (LIPIcs), Vol. 138 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 59:1\u201359:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS. 2019 .59 Amirhossein Kazeminia and Andrei A. Bulatov. 2019. Counting homomorphisms modulo a prime number. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919) (LIPIcs), Vol. 138. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 59:1\u201359:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.59"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/256509.256518"},{"key":"e_1_2_1_45_1","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups","volume":"7","author":"Larose Beno\u00eet","year":"2017","unstructured":"Beno\u00eet Larose . 2017 . Algebra and the complexity of digraph CSPs: A survey . In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 267\u2013285. Beno\u00eet Larose. 2017. Algebra and the complexity of digraph CSPs: A survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 267\u2013285."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.008"},{"key":"e_1_2_1_47_1","volume-title":"Retracts of graphs. Mathematical Systems in Economics","author":"Pesch Erwin","unstructured":"Erwin Pesch . 1988. Retracts of graphs. Mathematical Systems in Economics , Vol. 110 . Athen\u00e4um Verlag GmbH , Frankfurt am Main. xii+220 pages. Erwin Pesch. 1988. Retracts of graphs. Mathematical Systems in Economics, Vol. 110. Athen\u00e4um Verlag GmbH, Frankfurt am Main. xii+220 pages."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2012-11274-2"},{"key":"e_1_2_1_49_1","series-title":"Lecture Notes in Mathematics","volume-title":"Diophantine approximations and Diophantine equations","author":"Schmidt Wolfgang M.","unstructured":"Wolfgang M. Schmidt . 1991. Diophantine approximations and Diophantine equations . Lecture Notes in Mathematics , Vol. 1467 . Springer-Verlag , Berlin . viii+217 pages. DOI:https:\/\/doi.org\/10.1007\/BFb0098246 Wolfgang M. Schmidt. 1991. Diophantine approximations and Diophantine equations. Lecture Notes in Mathematics, Vol. 1467. Springer-Verlag, Berlin. viii+217 pages. DOI:https:\/\/doi.org\/10.1007\/BFb0098246"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2019.190.2.6"},{"key":"e_1_2_1_51_1","first-page":"46","article-title":"Hedetniemi\u2019s conjecture, 40 years later","volume":"54","author":"Tardif Claude","year":"2008","unstructured":"Claude Tardif . 2008 . Hedetniemi\u2019s conjecture, 40 years later . Graph Theory Notes NY 54 , 46 \u2013 57 (2008), 2. Claude Tardif. 2008. Hedetniemi\u2019s conjecture, 40 years later. Graph Theory Notes NY 54, 46\u201357 (2008), 2.","journal-title":"Graph Theory Notes NY"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1049"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397801"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.07.003"},{"key":"e_1_2_1_55_1","series-title":"Lecture Notes in Comput. Sci.","volume-title":"Combinatorial Algorithms","author":"Vikas Narayan","unstructured":"Narayan Vikas . 2018. Computational complexity relationship between compaction, vertex-compaction, and retraction . In Combinatorial Algorithms . Lecture Notes in Comput. Sci. , Vol. 10765 . Springer , Cham , 154\u2013166. Narayan Vikas. 2018. Computational complexity relationship between compaction, vertex-compaction, and retraction. In Combinatorial Algorithms. Lecture Notes in Comput. Sci., Vol. 10765. Springer, Cham, 154\u2013166."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.07.007"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3458040","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3458040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:39Z","timestamp":1750181079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3458040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3458040"],"URL":"https:\/\/doi.org\/10.1145\/3458040","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2020-04-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-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}