Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
Approximately Counting $H$-Colorings is $\#\mathrm{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 …