{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:22Z","timestamp":1750220782734,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714532"],"award-info":[{"award-number":["714532"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["334828"],"award-info":[{"award-number":["334828"]}],"id":[{"id":"10.13039\/100011199","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":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>G<\/jats:italic>\n            be a graph that contains an induced subgraph\n            <jats:italic>H<\/jats:italic>\n            . A\n            <jats:italic>retraction<\/jats:italic>\n            from\n            <jats:italic>G<\/jats:italic>\n            to\n            <jats:italic>H<\/jats:italic>\n            is a homomorphism from\n            <jats:italic>G<\/jats:italic>\n            to\n            <jats:italic>H<\/jats:italic>\n            that is the identity function on\n            <jats:italic>H<\/jats:italic>\n            . Retractions are very well studied: Given\n            <jats:italic>H<\/jats:italic>\n            , the complexity of deciding whether there is a retraction from an input graph\n            <jats:italic>G<\/jats:italic>\n            to\n            <jats:italic>H<\/jats:italic>\n            is completely classified, in the sense that it is known for which\n            <jats:italic>H<\/jats:italic>\n            this problem is tractable (assuming P \u2260 NP). Similarly, the complexity of (exactly) counting retractions from\n            <jats:italic>G<\/jats:italic>\n            to\n            <jats:italic>H<\/jats:italic>\n            is classified (assuming FP \u2260 #P). However, almost nothing is known about approximately counting retractions. Our first contribution is to give a complete trichotomy for approximately counting retractions to graphs without short cycles. The result is as follows: (1) Approximately counting retractions to a graph\n            <jats:italic>H<\/jats:italic>\n            of girth at least 5 is in FP if every connected component of\n            <jats:italic>H<\/jats:italic>\n            is a star, a single looped vertex, or an edge with two loops. (2) Otherwise, if every component is an irreflexive caterpillar or a partially bristled reflexive path, then approximately counting retractions to\n            <jats:italic>H<\/jats:italic>\n            is equivalent to approximately counting the independent sets of a bipartite graph\u2014a problem that is complete in the approximate counting complexity class RH \u03a0\n            <jats:sub>1<\/jats:sub>\n            . (3) Finally, if none of these hold, then approximately counting retractions to\n            <jats:italic>H<\/jats:italic>\n            is equivalent to approximately counting the satisfying assignments of a Boolean formula.\n          <\/jats:p>\n          <jats:p>\n            Our second contribution is to locate the retraction counting problem for each\n            <jats:italic>H<\/jats:italic>\n            in the complexity landscape of related approximate counting problems. Interestingly, our results are in contrast to the situation in the exact counting context. We show that the problem of approximately counting retractions is separated both from the problem of approximately counting homomorphisms and from the problem of approximately counting list homomorphisms\u2014whereas for exact counting all three of these problems are interreducible. We also show that the number of retractions is at least as hard to approximate as both the number of surjective homomorphisms and the number of compactions. In contrast, exactly counting compactions is the hardest of all of these exact counting problems.\n          <\/jats:p>","DOI":"10.1145\/3397472","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T10:13:38Z","timestamp":1591006418000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Approximately Counting Retractions"],"prefix":"10.1145","volume":"12","author":[{"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"University of Oxford, Wolfson Building, Parks Road, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Wolfson Building, Parks Road, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Wolfson Building, Parks Road, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90646-W"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.029"},{"volume-title":"Topics in Discrete Mathematics. Algorithms Combin.","author":"Borgs Christian","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.08.003"},{"volume-title":"Surveys in Combinatorics","year":"1999","author":"Dyer Martin","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/360708.360731"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958204.1958205"},{"key":"e_1_2_1_14_1","unstructured":"Jacob Focke Leslie Ann Goldberg and Stanislav \u017divn\u00fd. 2017. The complexity of counting surjective homomorphisms and compactions. CoRR abs\/1706.08786 (2017). Retrieved from http:\/\/arxiv.org\/abs\/1706.08786. A preliminary version of this work appeared in the Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1772-1781.  Jacob Focke Leslie Ann Goldberg and Stanislav \u017divn\u00fd. 2017. The complexity of counting surjective homomorphisms and compactions. CoRR abs\/1706.08786 (2017). Retrieved from http:\/\/arxiv.org\/abs\/1706.08786. A preliminary version of this work appeared in the Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1772-1781."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020551"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037381"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997580"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600917"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408363"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Comput. Sci.","volume-title":"Surjective H-colouring: New hardness results. In Unveiling Dynamics and Complexity","author":"Golovach Petr A.","year":"2017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-012-0164-0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.039"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300008494"},{"key":"e_1_2_1_25_1","unstructured":"Pavol Hell. 1973. Retractions des graphes. ProQuest LLC Ann Arbor MI. Retrieved from http:\/\/ezproxy-prd.bodleian.ox.ac.uk:2175\/openurl?url_ver&equals;Z39.88-2004&rft_val_fmt&equals;&equals;info:ofi\/fmt:kev:mtx:dissertation&res_dat&equals;&equals;xri:pqdiss&rft_dat&equals;&equals;xri:pqdiss:0289365. Ph.D. thesis Universite de Montreal.  Pavol Hell. 1973. Retractions des graphes. ProQuest LLC Ann Arbor MI. Retrieved from http:\/\/ezproxy-prd.bodleian.ox.ac.uk:2175\/openurl?url_ver&equals;Z39.88-2004&rft_val_fmt&equals;&equals;info:ofi\/fmt:kev:mtx:dissertation&res_dat&equals;&equals;xri:pqdiss&rft_dat&equals;&equals;xri:pqdiss:0289365. Ph.D. thesis Universite de Montreal."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066450"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/08"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004b. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications Vol. 28. Oxford University Press Oxford. DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001  Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004b. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications Vol. 28. Oxford University Press Oxford. DOI:http:\/\/dx.doi.org\/10.1093\/acprof:oso\/9780198528173.001.0001","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1987-025-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_2_1_33_1","unstructured":"Steven Kelk. 2003. On the Relative Complexity of Approximately Counting H-colourings. Ph.D. Dissertation. Warwick University.  Steven Kelk. 2003. On the Relative Complexity of Approximately Counting H -colourings. Ph.D. Dissertation. Warwick University."},{"key":"e_1_2_1_34_1","unstructured":"Ekkehard G. K\u00f6hler. 1999. Graphs without Asteroidal Triples. Ph.D. Dissertation. Technische Universit\u00e4t Berlin.  Ekkehard G. K\u00f6hler. 1999. Graphs without Asteroidal Triples. Ph.D. Dissertation. Technische Universit\u00e4t Berlin."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/256509.256518"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.09.002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.008"},{"key":"e_1_2_1_38_1","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing (2nd ed.). Cambridge University Press Cambridge.  Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing (2nd ed.). Cambridge University Press Cambridge."},{"key":"e_1_2_1_39_1","volume-title":"Mathematical Systems in Economics","volume":"110","author":"Pesch Erwin","year":"1988"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100027419"},{"key":"e_1_2_1_41_1","volume-title":"Lecture Notes in Mathematics","volume":"1467","author":"Schmidt Wolfgang M.","year":"1991"},{"volume-title":"Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, S. Michaelson and Robin Milner (Eds.)","year":"1976","author":"Schnorr Claus-Peter","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1049"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383522"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397801"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00034-5"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.07.003"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9720-9"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science. LIPIcs. Leibniz Int. Proc. Inform.","volume":"83","author":"Vikas Narayan","year":"2017"},{"volume-title":"Combinatorial Algorithms","series-title":"Lecture Notes in Computer Science","author":"Vikas Narayan","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1673203"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397472","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:33Z","timestamp":1750200093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3397472"],"URL":"https:\/\/doi.org\/10.1145\/3397472","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}