Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Approximately Counting H-Colourings is -Hard
verfasst von : Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.