Tree-depth and the Formula Complexity of Subgraph Isomorphism
Tree-depth and the Formula Complexity of Subgraph Isomorphism
复制标题
树的深度和子图同构的公式复杂度
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
D. Kush;Benjamin Rossman
对于一个固定的“模式”图\(G\)，有色\(G\)-子图同构问题（记为\(\text{SUB}(G)\)）是指，给定一个\(n\)个顶点的图\(H\)以及一个从\(V(H)\)到\(V(G)\)的着色，询问\(H\)是否包含\(G\)的一个正确着色的副本。这个问题的复杂性与\(P =?\ NP\)和\(L =?\ NL\)的参数化版本以及其他问题相关。一个首要目标是根据模式图\(G\)的自然不变量，在不同的计算模型下理解\(\text{SUB}(G)\)的复杂性。在本文中，我们在\(\text{SUB}(G)\)的公式复杂性和一个称为树深（记为\(\text{td}(G)\)）的不变量之间建立了紧密的关系。已知\(\text{SUB}(G)\)可由大小为\(O(n^{\text{td}(G)})\)的单调\(AC^{0}\)公式求解。我们的主要结果是对于单调或具有亚对数深度的公式，有一个\(n^{\widetilde{\Omega}(\text{td}(G)^{1/3})}\)的下界。这补充了李、拉兹博罗夫和罗斯曼[8]关于树宽和\(AC^{0}\)电路规模的一个下界。作为一个推论，它暗示了有限结构上一阶逻辑的一个更强的同态保持定理[14]。这个结果的技术核心是在\(G\)是高度为\(k\)的完全二叉树的特殊情况下的一个\(n^{\Omega(k)}\)下界，我们使用[15]中引入的路径集框架来建立这个下界。（一般模式的下界通过树深的一个近期的排除-子图特征[4]，[6]得到。）本文的其他结果扩展了路径集框架，并改进了\(G\)是路径时\(\text{SUB}(G)\)的平均情况公式规模的已知最佳上界和下界。
For a fixed “pattern” graph <tex>$G$</tex>, the colored <tex>$G$</tex>-subgraph isomorphism problem (denoted <tex>$\text{SUB}(G)$</tex>) asks, given an <tex>$n$</tex>-vertex graph <tex>$H$</tex> and a coloring <tex>$V(H)\rightarrow V(G)$</tex>, whether <tex>$H$</tex> contains a properly colored copy of <tex>$G$</tex>. The complexity of this problem is tied to parameterized versions of <tex>$P=?\ \ NP$</tex> and <tex>$L=?\ \ NL$</tex>, among other questions. An overarching goal is to understand the complexity of <tex>$\text{SUB}(G)$</tex>, under different computational models, in terms of natural invariants of the pattern graph <tex>$G$</tex>. In this paper, we establish a close relationship between the formula complexity of <tex>$\text{SUB}(G)$</tex> and an invariant known as tree-depth (denoted td (<tex>$G$</tex>)). <tex>$\text{SUB}(G)$</tex> is known to be solvable by monotone <tex>$AC^{0}$</tex> formulas of size <tex>$O(n^{\text{td}(G)})$</tex>. Our main result is an <tex>$n^{\widetilde{\Omega}(\text{td}(G)^{1/3})}$</tex> lower bound for formulas that are monotone or have sub-logarithmic depth. This complements a lower bound of Li, Razborov and Rossman [8] relating tree-width and AC° circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures [14]. The technical core of this result is an <tex>$n^{\Omega(k)}$</tex> lower bound in the special case where <tex>$G$</tex> is a complete binary tree of height <tex>$k$</tex>, which we establish using the pathset framework introduced in [15]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [4], [6].) Additional results of this paper extend the pathset framework and improve upon both, the best known upper and lower bounds on the average-case formula size of <tex>$\text{SUB}(G)$</tex> when <tex>$G$</tex> is a path.