APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD

We consider the problem of counting H-colorings 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 graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have a fully polynomial randomized approximation scheme (FPRAS). If this is so, then our result shows that for every graph H without trivial components, the H-coloring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk, and Paterson. They were able to show that approximately sampling H-colorings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on nonconstructive ideas using the work of Lovasz.