Approximately Counting Graph Homomorphisms and Retractions (Invited Talk)

Abstract

A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves the edges of G in the sense that every edge of G is mapped to an edge of H. By changing the target graph H, we can capture interesting structures in G. For example, homomorphisms from G to a k-clique H correspond to the proper k-colourings of G. There has been a lot of algorithmic work on the problem of (approximately) counting homomorphisms. The goal is to figure out for which graphs H the problem of approximately counting homomorphisms to H is algorithmically feasible. This talk will survey what is known. Despite much work, there are still plenty of open problems. We will discuss the problem of approximately counting list homomorphisms (where the input specifies, for each vertex of G, the list of vertices of H to which it can be mapped). Because the lists add extra expressibility, it is easier to prove that counting homomorphisms to a particular graph H is intractable. In fact, we have a full trichotomy (joint work with Galanis and Jerrum, 2017). Here, the complexity of homomorphism-counting is related to certain hereditary graph classes. The trichotomy will be explained in the talk - no prior knowledge of the area will be assumed. In more recent work, with Focke and Živn{ý}, we have investigated the complexity of counting retractions to H - this problem falls between homomorphism-counting and list-homomorphism counting. Here we have only a partial classification, which applies to all square-free graphs H. So again, there are plenty of open problems.