The Complexity of Approximately Counting Retractions

DOI10.1145/3397472zbMath1499.68143OpenAlexW3123485485MaRDI QIDQ5053066

Jacob Focke, Stanislav Živný, Leslie Ann Goldberg

Publication date: 5 December 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3397472

zbMATH Keywords

graph homomorphismsapproximate countingcounting complexitysurjective homomorphismsretractionsgraph compactions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

This page was built for publication: The Complexity of Approximately Counting Retractions