The complexity of approximately counting retractions to square-free graphs
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 trichoto...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|