Journal article
The complexity of approximately counting retractions to square-free graphs
- 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 #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new #BIS-easiness results, we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs that were previously unresolved.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 762.7KB, Terms of use)
-
- Publisher copy:
- 10.1145/3458040
Authors
- Publisher:
- Association for Computing Machinery
- Journal:
- ACM Transactions on Algorithms More from this journal
- Volume:
- 17
- Issue:
- 3
- Article number:
- 22
- Publication date:
- 2021-07-12
- Acceptance date:
- 2021-03-01
- DOI:
- EISSN:
-
1549-6333
- ISSN:
-
1549-6325
- Language:
-
English
- Keywords:
- Pubs id:
-
1168844
- Local pid:
-
pubs:1168844
- Deposit date:
-
2021-03-20
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2021
- Rights statement:
- © 2021 Association for Computing Machinery
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Association for Computing Machinery at https://doi.org/10.1145/3458040
If you are the owner of this record, you can report an update to it here: Report update to this record