The Complexity of Approximately Counting Retractions to Square-free Graphs

DOI10.1145/3458040zbMath1499.68142arXiv1907.02319OpenAlexW3185350268MaRDI QIDQ5032031

Leslie Ann Goldberg, Stanislav Živný, Jacob Focke

Publication date: 16 February 2022

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

Full work available at URL: https://arxiv.org/abs/1907.02319

zbMATH Keywords

graph homomorphismsapproximate countingcounting complexityretractionssquare-free graphs

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 to Square-free Graphs