Approximately counting H-colourings is BIS-Hard

Journal article

We consider counting H-colourings from an input graph G to a target graph H. We show that for any fixed graph H without trivial components, this is as hard as the well-known problem #BIS, 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 an FPRAS. If this is so, then our result shows that for every graph H without tr...

Expand abstract

Authors: Galanis, A; Goldberg, L; Jerrum, M

• Publication status: Submitted
• Peer review status: Peer reviewed
• Language: English