The Complexity of Approximately Counting Retractions

DOI10.1137/1.9781611975482.133zbMath1432.68179arXiv1807.00590OpenAlexW4245145830MaRDI QIDQ5236320

Jacob Focke, Stanislav Živný, Leslie Ann Goldberg

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

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)

Related Items (1)

Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

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