Goldberg, Leslie Ann
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 kclique H correspond to the proper kcolourings 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 homomorphismcounting 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 homomorphismcounting and listhomomorphism counting. Here we have only a partial classification, which applies to all squarefree graphs H. So again, there are plenty of open problems.
BibTeX  Entry
@InProceedings{goldberg:LIPIcs.FSTTCS.2021.3,
author = {Goldberg, Leslie Ann},
title = {{Approximately Counting Graph Homomorphisms and Retractions}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {3:13:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772150},
ISSN = {18688969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15514},
URN = {urn:nbn:de:0030drops155146},
doi = {10.4230/LIPIcs.FSTTCS.2021.3},
annote = {Keywords: Graph homomorphisms, counting}
}
29.11.2021
Keywords: 

Graph homomorphisms, counting 
Seminar: 

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Issue date: 

2021 
Date of publication: 

29.11.2021 