2026-07-24T01:45:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6326 2024-03-06T10:37:43Z ddc:004 open_access

A Complexity Trichotomy for Approximately Counting List H-Colourings Galanis, Andreas Goldberg, Leslie Ann Jerrum, Mark approximate counting graph homomorphisms list colourings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Galanis and Leslie Ann Goldberg and Mark Jerrum 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.46 urn:nbn:de:0030-drops-63262 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.46 eng https://creativecommons.org/licenses/by/3.0/legalcode