Journal article icon

Journal article

Approximately counting H-colourings is #BIS-hard

Abstract:

We consider the problem of counting H-colourings 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 a 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 t...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1137/15M1020551

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Computing Journal website
Volume:
45
Issue:
3
Pages:
680–711
Publication date:
2016
DOI:
EISSN:
1095-7111
ISSN:
0097-5397
URN:
uuid:dc2dc294-1c4d-4bb6-87ee-7acf0b3c8fe8
Source identifiers:
606794
Local pid:
pubs:606794

Terms of use


Metrics



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

TO TOP