标题： 单调有界深度的同态多项式复杂性 显示英文标题

标题： Monotone Bounded-Depth Complexity of Homomorphism Polynomials

摘要： 对于每个固定的图 $H$，已知可以从 $H$ 的同态计数以及多彩的 $H$-子图计数在 $O(n^{t+1})$ 时间内确定，适用于顶点数为 $n$ 的输入图 $G$，其中 $t$ 是 $H$ 的树宽。 另一方面，$n^{o(t / \log t)}$ 的运行时间将反驳指数时间假设。 Komarath、Pandey 和 Rahul (Algorithmica, 2023) 研究了这些计数问题的代数变体，即固定图 $H$ 的同态和子图 $\textit{多项式}$。 这些多项式是上述计数对象的加权和，其中每个对象的权重为其所含边对应变量的乘积。 如 Komarath 等人所示，$H$ 的同态多项式的 $\textit{单调}$ 电路复杂度为 $\Theta(n^{\mathrm{tw}(H)+1})$。 在本文中，我们描述了单调$\textit{有界深度}$电路对于同态和彩色子图多项式的威力。 这引导我们发现了一种自然的图参数层次结构 $\mathrm{tw}_\Delta(H)$，对于固定的 $\Delta \in \mathbb N$，当要求底层树的深度最多为 $\Delta$时，它捕捉了 $H$ 的树分解宽度。 我们证明了计算 $H$ 的同态多项式的深度为 $\Delta$ 的单调电路需要大小为 $\Theta(n^{\mathrm{tw}_\Delta(H^{\dagger})+1})$，其中 $H^{\dagger}$ 是从 $H$ 中去掉所有度数为 $1$ 的顶点所得到的图。 这使我们能够通过图论论证得出单调有界深度电路的最优深度层次定理。 显示英文摘要

摘要： For every fixed graph $H$, it is known that homomorphism counts from $H$ and colorful $H$-subgraph counts can be determined in $O(n^{t+1})$ time on $n$-vertex input graphs $G$, where $t$ is the treewidth of $H$. On the other hand, a running time of $n^{o(t / \log t)}$ would refute the exponential-time hypothesis. Komarath, Pandey and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph $\textit{polynomials}$ for fixed graphs $H$. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the $\textit{monotone}$ circuit complexity of the homomorphism polynomial for $H$ is $\Theta(n^{\mathrm{tw}(H)+1})$. In this paper, we characterize the power of monotone $\textit{bounded-depth}$ circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters $\mathrm{tw}_\Delta(H)$, for fixed $\Delta \in \mathbb N$, which capture the width of tree-decompositions for $H$ when the underlying tree is required to have depth at most $\Delta$. We prove that monotone circuits of product-depth $\Delta$ computing the homomorphism polynomial for $H$ require size $\Theta(n^{\mathrm{tw}_\Delta(H^{\dagger})+1})$, where $H^{\dagger}$ is the graph obtained from $H$ by removing all degree-$1$ vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.