Paper Info
Title
The Exponential-Time Complexity Of Counting (Quantum) Graph Homomorphisms
Abstract
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 Zivny (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 Lovasz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.
Year
DOI
Venue
2019
10.1007/978-3-030-30786-8_28
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019)
Keywords
Field
DocType
Graph homomorphisms, Exponential-time hypothesis, Counting complexity, Complexity dichotomy, Surjective homomorphisms
Linear combination,Discrete mathematics,Graph,Combinatorics,Dichotomy,Computer science,Quantum graph,Exponential complexity,Homomorphism,Surjective function,Exponential time hypothesis
Conference
Volume
ISSN
Citations 
11789
0302-9743
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Hubie Chen141840.82
Radu Curticapean2708.75
Holger Dell322016.74