论文标题
在有限顺序有限领域的计数（量子 - ）图（量子 - ）
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
论文作者
论文摘要
我们研究了从输入图$ g $到固定（量子）图$ \ bar {h} $在任何有限级阶段$ \ mathbb {z} _p $中计算固定（量子）图$ \ bar {h} $的同态数量的问题。 Faben和Jerrum [Toc'15]引入了图形$ H $的子问题，其复杂性受到了一系列不断增长的研究文章的影响，例如在本文的会议版本之后，Focke，Goldberg，Roth和Zivný[Sidma'21]以及Bulatov和Kazeminia [Stoc'22]的工作。我们的贡献是三倍。首先，我们将量子图的研究介绍给模块化计数同态的研究。我们表明，量子图的复杂性$ \ bar {h} $倒在维度1：图形上的复杂性标准。其次，为了证明棘手性的案例，我们对双方图的研究进一步降低。最后，我们为所有两分（$ k_ {3,3} \ backslash \ {e \} $，$ {domino} $）建立了二分法 - 通过一项彻底的结构研究，结合了本地和全球参数。该结果将所有结果都归于所有主要模量已知的两分图，并显着扩展了它们。即使对于$ P $等于$ 2 $的子问题，这也建立了新的结果。
We study the problem of counting the number of homomorphisms from an input graph $G$ to a fixed (quantum) graph $\bar{H}$ in any finite field of prime order $\mathbb{Z}_p$. The subproblem with graph $H$ was introduced by Faben and Jerrum [ToC'15] and its complexity is subject to a growing series of research articles, e.g. the work of Focke, Goldberg, Roth, and Zivný [SIDMA'21] and the work of Bulatov and Kazeminia [STOC'22], subsequent to this article's conference version. 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 $\bar{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}\backslash\{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$ equal to $2$, this establishes new results.
