The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Many graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy for such problems, classifying which target graphs render the problem polynomial-time solvable or #P-hard. In this paper, we give a new and shorter proof of this theorem, with previously unknown tight lower bounds under the exponential-time hypothesis. We similarly strengthen complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs. Both results crucially rely on our main contribution, a complexity dichotomy for evaluating linear combinations of homomorphism numbers to fixed graphs. In the terminology of Lovász (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science : 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers
Publication date2019
ISBN (Print)978-3-030-30785-1
ISBN (Electronic)978-3-030-30786-8
Publication statusPublished - 2019
SeriesLecture Notes in Computer Science


Dive into the research topics of 'The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms'. Together they form a unique fingerprint.

Cite this