论文标题
树深度和子图同构的配方复杂性
Tree-depth and the Formula Complexity of Subgraph Isomorphism
论文作者
论文摘要
For a fixed "pattern" graph $G$, the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$.此问题的复杂性与$ \ mathit {p} $ $ {=}？$ $ \ $ \ $ \ MATHIT {NP} $和$ \ MATHIT {L} $ $ {=}？$ $ $ \ MATHIT {NL} $等参数化版本有关。一个总体目标是了解$ \ mathrm {sub}（g）$的复杂性，在不同的计算模型下，就图案图$ g $的自然不变性而言。 在本文中，我们建立了$ \ mathrm {subrm {sub} $的$ \ textIt {公式复杂性} $与称为$ \ textit {tree-depth} $（表示$ \ mathrm {td}（g）$）的$ \ textit {公式复杂性} $。已知$ \ mathrm {sub}（g）$可通过monotone $ \ mathit {ac^0} $ size $ o $ o（n^{\ mathrm {td}（g）}）$解决。我们的主要结果是$ n^{\tildeΩ（\ mathrm {td}（g）^{1/3}）} $对于单调$ \ textIt {或} $的公式的下限，具有子量的深度。这补充了Li，Razborov和Rossman（Sicomp 2017）的下限，将树宽度和$ \ Mathit {ac^0} $电路大小。作为推论，它暗示了有限结构的一阶逻辑的更强的同态保存定理（Rossman，ITCS 2017）。 该结果的技术核心是在特殊情况下$ n^{ω（k）} $下限，其中$ g $是一棵完整的高度$ k $的二进制二进制树，我们使用$ \ textit {PathSet Framework} $在（Rossman，SiCOMP，SICOMP 2018）中建立。 （一般模式的下限是通过最近排除的树深度表征（Czerwiński等人，ARXIV：1904.13077）。）本文的其他结果扩展了路径集框架，并在平均公式的上限和最低范围上改进了$ \ mathrm $ \ mathrm a s $ a s $ a s $ a $ a $ a $ a $ a $ a $。
For a fixed "pattern" graph $G$, the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ${=}?$ $\mathit{NL}$, among other questions. An overarching goal is to understand the complexity of $\mathrm{SUB}(G)$, under different computational models, in terms of natural invariants of the pattern graph $G$. In this paper, we establish a close relationship between the $\textit{formula complexity}$ of $\mathrm{SUB}$ and an invariant known as $\textit{tree-depth}$ (denoted $\mathrm{td}(G)$). $\mathrm{SUB}(G)$ is known to be solvable by monotone $\mathit{AC^0}$ formulas of size $O(n^{\mathrm{td}(G)})$. Our main result is an $n^{\tildeΩ(\mathrm{td}(G)^{1/3})}$ lower bound for formulas that are monotone $\textit{or}$ have sub-logarithmic depth. This complements a lower bound of Li, Razborov and Rossman (SICOMP 2017) relating tree-width and $\mathit{AC^0}$ circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures (Rossman, ITCS 2017). The technical core of this result is an $n^{Ω(k)}$ lower bound in the special case where $G$ is a complete binary tree of height $k$, which we establish using the $\textit{pathset framework}$ introduced in (Rossman, SICOMP 2018). (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth (Czerwiński et al, arXiv:1904.13077).) 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 $\mathrm{SUB}(G)$ when $G$ is a path.
