The Complexity of Approximately Counting Retractions to Square-free Graphs

DOI10.1145/3458040MaRDI QIDQ5032031zbMATH OpenOpenAlexFDO

Authors Jacob Focke, Leslie Ann Goldberg, S. Zivny

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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30)

Abstract: A retraction is a homomorphism from a graph $G$ to an induced subgraph $H$ of $G$ that is the identity on $H$. In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length $4$). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class $$. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new $$-easiness results we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs which were previously unresolved.

Recommendations

• The complexity of approximately counting retractions
• The complexity of approximately counting retractions
• scientific article; zbMATH DE number 1445311
• The complexity of counting in sparse, regular, and planar graphs
• scientific article; zbMATH DE number 1545676
• Bounding the size of square-free subgraphs of the hypercube
• On a certain complexity estimate in graph theory
• Some problems on approximate counting in graphs and matroids

Cited in

(2)

• The complexity of approximately counting retractions
• The complexity of approximately counting retractions

This page was built for publication: The Complexity of Approximately Counting Retractions to Square-free Graphs

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