Abstract
We examine the computational complexity of approximately counting the list Hcolourings of a graph. We discover a natural graphtheoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list Hcolourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list Hcolourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a wellstudied problem which is believed to be of intermediate complexity  it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list Hcolourings is complete for #P with respect to approximationpreserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely selfcontained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the boundeddegree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.
BibTeX  Entry
@InProceedings{galanis_et_al:LIPIcs:2016:6326,
author = {Andreas Galanis and Leslie Ann Goldberg and Mark Jerrum},
title = {{A Complexity Trichotomy for Approximately Counting List HColourings}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {46:146:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6326},
URN = {urn:nbn:de:0030drops63262},
doi = {10.4230/LIPIcs.ICALP.2016.46},
annote = {Keywords: approximate counting, graph homomorphisms, list colourings}
}
Keywords: 

approximate counting, graph homomorphisms, list colourings 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

17.08.2016 