Back to Search
Start Over
The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms
- Source :
- Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851, WG
- Publication Year :
- 2019
- Publisher :
- Springer International Publishing, 2019.
-
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 \(\#\mathrm {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 Lovasz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.
- Subjects :
- Discrete mathematics
Exponential complexity
Exponential time hypothesis
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Graph
Surjective function
010201 computation theory & mathematics
020204 information systems
Quantum graph
0202 electrical engineering, electronic engineering, information engineering
Homomorphism
Linear combination
Mathematics
Subjects
Details
- ISBN :
- 978-3-030-30785-1
- ISBNs :
- 9783030307851
- Database :
- OpenAIRE
- Journal :
- Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851, WG
- Accession number :
- edsair.doi...........bcafef1717e875bd7153582fb2256111