The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms
Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-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 language | English |
---|---|
Title of host publication | Graph-Theoretic Concepts in Computer Science : 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers |
Publisher | Springer |
Publication date | 2019 |
Pages | 364-378 |
ISBN (Print) | 978-3-030-30785-1 |
ISBN (Electronic) | 978-3-030-30786-8 |
DOIs | |
Publication status | Published - 2019 |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 11789 |
ISSN | 0302-9743 |
Downloads
No data available
ID: 84682753