Advertisement
Published in:
2015 | OriginalPaper | Chapter
Approximately Counting H-Colourings is -Hard
Authors : Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Published in: Automata, Languages, and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$$\#\mathrm {BIS}$$
#
BIS
, the problem of (approximately) counting independent sets in a bipartite graph.
$$\#\mathrm {BIS}$$
#
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 trivial components, the
H
-colouring 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
-colourings is
$$\#\mathrm {BIS}$$
#
BIS
-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovász. The full version is available at
arxiv.org/abs/1502.01335
. The theorem numbering here matches the full version.