Spring 2016

The Computational Complexity of Counting List H-Colourings, and Related Problems

Wednesday, March 30th, 2016 9:30 am10:15 am

Add to Calendar

H-colourings of a graph G (a.k.a. homomorphisms from G to H) generalise familiar proper vertex colourings of G.  More than 15 years ago, Dyer and Greenhill presented a dichotomy for exactly counting H-colourings.  That was for exact counting, and, even now, there is only a partial complexity classification for approximate counting. A familiar theme in the study of CSPs is that the “conservative” case is often easier to resolve.  This is one reason to look at list H-colourings.  The decision problem for list H-colourings was studied by Feder, Hell and Huang, who proved a dichotomy result.  In this talk, I’ll present a classification for the problem of approximately counting list H-colourings of a graph, and briefly consider weighted variants.

This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford), and others.