图问题的核化与子图测试：顶点覆盖视角

### 图问题的核化与子图测试：顶点覆盖视角 在图论算法领域，研究图问题的多项式核化以及子图和子式测试的复杂性是重要的课题。下面我们将深入探讨相关问题，包括顶点删除问题、最大诱导子图问题以及不同类型图的子图和子式测试。 #### 顶点删除问题的核化 考虑顶点删除问题，其形式为“Deletion Distance To Π - free (vc)”。 - **输入**：图 $G$ 及其顶点覆盖 $X \subseteq V(G)$，整数 $k \geq 1$。 - **参数**：顶点覆盖的大小 $|X|$。 - **问题**：是否存在大小至多为 $k$ 的集合 $S \subseteq V(G)$，使得 $G - S$ 不包含 $\Pi$ 中的图作为诱导子图。 有如下定理： **定理 1**：若 $\Pi$ 满足以下条件： 1. $\Pi$ 由 $c_{\Pi}$ 个邻接关系刻画。 2. $\Pi$ 中的每个图至少包含一条边。 3. 存在非负多项式 $p: \mathbb{N} \to \mathbb{N}$，使得 $\Pi$ 中的所有图 $G$ 都包含诱导子图 $G' \in \Pi$，且 $|V(G')| \leq p(vc(G'))$。 则“Deletion Distance To Π - free (vc)”问题有一个包含 $O((x + p(x))x^{c_{\Pi}})$ 个顶点的核，其中 $x := |X|$。 以下是满足该定理的问题列表： | 问题 | $\Pi$ | $c_{\Pi}$ | | --- | --- | --- | | Vertex Cover | $\{K_2\}$ | 1 | | Odd Cycle Transversal | 包含奇环的图 | 2 | | Chordal Deletion | 有弦less环的图 | 3 | | Planarization | 有 $K_5$ 或 $K_{3,3}$ 子式的图 | 4 | | $\eta$-Transversal | 树宽 $> \eta$ 的图 | $f(\eta)$ | | F - Minor - Free Deletion | 有 $H \in F$ 子式的图 | $\max_{H \in F} \Delta(H)$ | **证明思路**： 对于输入实例 $(G, X, k)$，若 $k \geq |X|$，则为肯定实例，因为移除 $X$ 得到无边图，根据条件 2 不包含 $\Pi$ 中的诱导子图。所以假设 $k < |X|$。令 $G'$ 是 $Reduce(G, X, k + p(|X|), c_{\Pi})$ 的结果，返回实例 $(G', X, k)$。可证明输出实例与输入实例等价。 #### 最大诱导子图问题的核化 研究“Largest Induced Π - subgraph (vc)”问题： - **输入**：图 $G$ 及其顶点覆盖 $X \subseteq V(G)$，整数 $k \geq 1$。 - **参数**：顶点覆盖的大小 $|X|$。 - **问题**：是否存在大小至少为 $k$ 的集合 $P \subseteq V(G)$，使得 $G[P] \in \Pi$。 有如下定理： **定理 2**：若 $\Pi$ 满足： 1. $\Pi$ 由 $c_{\Pi}$ 个邻接关系刻画。 2. 存在非负多项式 $p: \mathbb{N} \to \mathbb{N}$，使得对于 $\Pi$ 中的所有图 $G$，$|V(G)| \leq p(vc(G))$。 则“Largest Induced Π - subgraph (vc)”问题有一个包含 $O(p(|X|)|X|^{c_{\Pi}})$ 个顶点的核。 满足该定理的问题如下表所示： | 问题 | $\Pi$ | $c_{\Pi}$ | | --- | --- | --- | | Long Cycle | 有哈密