Conference item icon

Conference item

A complexity trichotomy for approximately counting list H-colourings

Abstract:

We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the pro...

Expand abstract
Publication status:
Published
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
Publisher:
Schloss Dagstuhl Publisher's website
Journal:
ICALP2016: 43rd International Colloquium on Automata, Languages and Programming Journal website
Host title:
ICALP2016: 43rd International Colloquium on Automata, Languages and Programming
Publication date:
2016-08-17
Acceptance date:
2016-04-14
EISSN:
1868-8969
ISSN:
1868-8969
Source identifiers:
619033
Keywords:
Pubs id:
pubs:619033
UUID:
uuid:c523559f-77f7-49f5-aef4-466b64247625
Local pid:
pubs:619033
Deposit date:
2016-05-02

Terms of use


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