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
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Host title:
- ICALP2016: 43rd International Colloquium on Automata, Languages and Programming
- Journal:
- ICALP2016: 43rd International Colloquium on Automata, Languages and Programming Journal website
- Publication date:
- 2016-08-17
- Acceptance date:
- 2016-04-14
- EISSN:
-
1868-8969
- ISSN:
-
1868-8969
Item Description
- Keywords:
- Pubs id:
-
pubs:619033
- UUID:
-
uuid:c523559f-77f7-49f5-aef4-466b64247625
- Local pid:
- pubs:619033
- Source identifiers:
-
619033
- Deposit date:
- 2016-05-02
Terms of use
- Copyright holder:
- Galanis et al
- Copyright date:
- 2016
- Notes:
-
Copyright © Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum;
licensed under Creative Commons License CC-BY. This article was presented at the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) and is available online at [10.4230/LIPIcs.ICALP.2016.46].
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record