License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.91
URN: urn:nbn:de:0030-drops-141608
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14160/
Lagodzinski, J. A. Gregor ;
Göbel, Andreas ;
Casel, Katrin ;
Friedrich, Tobias
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
Abstract
We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph ̄{H} in any finite field of prime order ℤ_p. The subproblem with graph H was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold.
First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph ̄{H} collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite (K_{3,3}$1{e}, {domino})-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with p = 2 this establishes new results.
BibTeX - Entry
@InProceedings{lagodzinski_et_al:LIPIcs.ICALP.2021.91,
author = {Lagodzinski, J. A. Gregor and G\"{o}bel, Andreas and Casel, Katrin and Friedrich, Tobias},
title = {{On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {91:1--91:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14160},
URN = {urn:nbn:de:0030-drops-141608},
doi = {10.4230/LIPIcs.ICALP.2021.91},
annote = {Keywords: Algorithms, Theory, Quantum Graphs, Bipartite Graphs, Graph Homomorphisms, Modular Counting, Complexity Dichotomy}
}
|
Keywords: |
|
Algorithms, Theory, Quantum Graphs, Bipartite Graphs, Graph Homomorphisms, Modular Counting, Complexity Dichotomy |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
