Approximately counting H-colourings is #BIS-hard
We consider the problem of counting H-colourings from an input graph G to a target graph H. We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite gr...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Journal article |
| Vydáno: |
Society for Industrial and Applied Mathematics
2016
|