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
|
| _version_ | 1826280700202975232 |
|---|---|
| author | Focke, J Goldberg, L Živný, S |
| author_facet | Focke, J Goldberg, L Živný, S |
| author_sort | Focke, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:17:38Z |
| format | Journal article |
| id | oxford-uuid:7b675d0a-13a5-4916-9251-bd125017fe79 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:17:38Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:7b675d0a-13a5-4916-9251-bd125017fe792022-03-26T20:50:32ZThe complexity of approximately counting retractions to square-free graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7b675d0a-13a5-4916-9251-bd125017fe79EnglishSymplectic ElementsAssociation for Computing Machinery2021Focke, JGoldberg, LŽivný, SA 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. |
| spellingShingle | Focke, J Goldberg, L Živný, S The complexity of approximately counting retractions to square-free graphs |
| title | The complexity of approximately counting retractions to square-free graphs |
| title_full | The complexity of approximately counting retractions to square-free graphs |
| title_fullStr | The complexity of approximately counting retractions to square-free graphs |
| title_full_unstemmed | The complexity of approximately counting retractions to square-free graphs |
| title_short | The complexity of approximately counting retractions to square-free graphs |
| title_sort | complexity of approximately counting retractions to square free graphs |
| work_keys_str_mv | AT fockej thecomplexityofapproximatelycountingretractionstosquarefreegraphs AT goldbergl thecomplexityofapproximatelycountingretractionstosquarefreegraphs AT zivnys thecomplexityofapproximatelycountingretractionstosquarefreegraphs AT fockej complexityofapproximatelycountingretractionstosquarefreegraphs AT goldbergl complexityofapproximatelycountingretractionstosquarefreegraphs AT zivnys complexityofapproximatelycountingretractionstosquarefreegraphs |