Graph algorithms and the complexity of counting

29^th November 2016, 13:00 Ashton Lecture Theater
Prof. Leslie Ann Goldberg
Professor of Computer Science
Senior Research Fellow, St Edmund Hall
E: leslie.goldberg@cs.ox.ac.uk
T: +44 (0)1865 610755

Room 330, Wolfson Building, Parks Road, Oxford OX1 3QD

Abstract

The field of "computational counting" considers counting problems such as "how many proper 3-colourings does an input graph have"? It is well-known that this particular problem is #P-hard to solve
exactly, and it is also clear that it is at least NP-hard to solve approximately (since it is NP-hard to tell whether the answer is zero). Since approximate counting arises in many applications (such as computing
probabilities and partition functions) there is a lot of research aimed at classifying counting problems, to see which ones can be solved approximately. This talk will contain a survey/background of the area, but
I will also tell you about a recent result, which is joint work with Andreas Galanis and Mark Jerrum, which completely classifies a family of (approximate) counting problems. The problems involve counting homomorphisms to a fixed graph~$H$ (I'll tell you what that means in the talk!) and it turns out that work on hereditary graph classes makes it possible to completely determine, for a given~$H$, the complexity of the corresponding counting problem.