论文标题
图同态多项式：算法和复杂性
Graph Homomorphism Polynomials: Algorithms and Complexity
论文作者
论文摘要
我们研究同态多项式，它们是多项式，列举了从图案图$ h $到$ n $ vertex图的所有同态。这些多项式最近因在几种用于计数和检测图形模式的新算法中的关键作用而引起了很多关注，还用于获取用于代数复杂性类别的天然多项式家庭$ \ Mathsf {vbp} $，$ \ \ \ \ \ \ \ \ \ thssf {vp} $，and $ \ mathsf} $ {vn。我们发现，在单调设置中，公式复杂性，ABP复杂性和此类多项式家族的电路复杂性分别以图形图的TreeDeppth，路径宽和树宽分别为特征。 此外，我们使用我们的表征建立了一个单一的统一框架，以收集通过不同方法独立获得的几个已知结果。例如，我们在单调设置中获得了电路，ABP和公式之间的超级分离分离，在该设置中，分隔班级的多项式家族都对应于精心研究的组合问题。此外，我们的证明重新发现了这些模型之间的细粒度分离，以换取恒定的多项式。该表征还产生了新的时空有效算法，用于几种模式检测和计数问题。
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph $H$ to $n$-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes $\mathsf{VBP}$, $\mathsf{VP}$, and $\mathsf{VNP}$. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials. The characterization additionally yields new space-time efficient algorithms for several pattern detection and counting problems.
