Journal article icon

Journal article

Approximately counting H-colourings is BIS-Hard

Abstract:

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
Publication status:
Submitted
Peer review status:
Peer reviewed

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Goldberg, L
Grant:
334828
More from this funder
Funding agency for:
Galanis, A
Grant:
334828
Language:
English
UUID:
uuid:3b63520c-67f3-4f9b-aa2f-debfebf40793
Local pid:
ora:11291
Deposit date:
2015-04-29

Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP