ITU

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

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

Standard

The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. / Chen, Hubie; Curticapean, Radu-Cristian; Dell, Holger.

Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers. Springer, 2019. p. 364-378 (Lecture Notes in Computer Science, Vol. 11789).

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

Harvard

Chen, H, Curticapean, R-C & Dell, H 2019, The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. in Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers. Springer, Lecture Notes in Computer Science, vol. 11789, pp. 364-378. https://doi.org/10.1007/978-3-030-30786-8_28

APA

Chen, H., Curticapean, R-C., & Dell, H. (2019). The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. In Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers (pp. 364-378). Springer. Lecture Notes in Computer Science Vol. 11789 https://doi.org/10.1007/978-3-030-30786-8_28

Vancouver

Chen H, Curticapean R-C, Dell H. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. In Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers. Springer. 2019. p. 364-378. (Lecture Notes in Computer Science, Vol. 11789). https://doi.org/10.1007/978-3-030-30786-8_28

Author

Chen, Hubie ; Curticapean, Radu-Cristian ; Dell, Holger. / The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers. Springer, 2019. pp. 364-378 (Lecture Notes in Computer Science, Vol. 11789).

Bibtex

@inproceedings{91ddb7bcd6e04102936a80682b0242f0,
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 {\v Z}ivn{\'y} (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{\'a}sz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.",
author = "Hubie Chen and Radu-Cristian Curticapean and Holger Dell",
year = "2019",
doi = "10.1007/978-3-030-30786-8_28",
language = "English",
isbn = "978-3-030-30785-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "364--378",
booktitle = "Graph-Theoretic Concepts in Computer Science",
address = "Germany",

}

RIS

TY - GEN

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

AU - Chen, Hubie

AU - Curticapean, Radu-Cristian

AU - Dell, Holger

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-30786-8_28

DO - 10.1007/978-3-030-30786-8_28

M3 - Article in proceedings

SN - 978-3-030-30785-1

T3 - Lecture Notes in Computer Science

SP - 364

EP - 378

BT - Graph-Theoretic Concepts in Computer Science

PB - Springer

ER -

ID: 84682753