ITU

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

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

View graph of relations

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
PublisherSpringer
Publication date2019
Pages364-378
ISBN (Print)978-3-030-30785-1
ISBN (Electronic)978-3-030-30786-8
DOIs
Publication statusPublished - 2019
SeriesLecture Notes in Computer Science
Volume11789
ISSN0302-9743

Downloads

No data available

ID: 84682753