Approximately Counting Graph Homomorphisms and Retractions (Invited Talk)

Author Leslie Ann Goldberg



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.3.pdf
  • Filesize: 341 kB
  • 1 pages

Document Identifiers

Author Details

Leslie Ann Goldberg
  • University of Oxford, UK

Cite AsGet BibTex

Leslie Ann Goldberg. Approximately Counting Graph Homomorphisms and Retractions (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.3

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Graph homomorphisms
  • counting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail