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: | , , |
|---|---|
| 格式: | Journal article |
| 語言: | English |
| 出版: |
Association for Computing Machinery
2021
|