The complexity of approximately counting retractions

DOI10.1145/3397472MaRDI QIDQ5053066zbMATH OpenOpenAlexFDO

Authors Jacob Focke, Leslie Ann Goldberg, S. Zivny

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

approximate countingcounting complexitygraph compactionsgraph homomorphismsretractionssurjective homomorphisms

Mathematics Subject Classification ID

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

Recommendations

• The complexity of approximately counting retractions
• The Complexity of Approximately Counting Retractions to Square-free Graphs
• Retractions to Pseudoforests
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• A complexity trichotomy for approximately counting list H-colourings

Cited in

(2)

• The Complexity of Approximately Counting Retractions to Square-free Graphs
• The complexity of approximately counting retractions

This page was built for publication: The complexity of approximately counting retractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5053066)