License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.46
URN: urn:nbn:de:0030-drops-63262
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6326/
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Jerrum, Mark
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 problem of approximately counting independent sets in a bipartite graph. This is a well-studied 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 H-colourings is complete for #P with respect to approximation-preserving 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 self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree 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 H-Colourings}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {46:1--46:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6326},
URN = {urn:nbn:de:0030-drops-63262},
doi = {10.4230/LIPIcs.ICALP.2016.46},
annote = {Keywords: approximate counting, graph homomorphisms, list colourings}
}
|
Keywords: |
|
approximate counting, graph homomorphisms, list colourings |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
