图问题的核化算法与相关结果研究

### 图问题的核化算法与相关结果研究 #### 1. 最长路径问题与相关问题的核化复杂度 在图论问题中，最长路径问题是一个经典的问题。给定一个图 $G = (V, E)$，最长路径问题询问是否存在一条长度至少为 $k$ 的简单路径（即没有重复顶点的路径）。下面将探讨它与 SWCS 和 $\ell$-RCS 问题的核化复杂度关系。 ##### 1.1 SWCS 问题的核化复杂度 - **实例构造**：设 $G = (V, E)$ 是最长路径问题的一个实例，其中 $V = \{v_1, \ldots, v_q\}$。定义字母表 $\Sigma = \{w_{i,1}, w_{i,2} : v_i \in V, 1 \leq i \leq q\} \cup \{w_{0,1}, w_{0,2}, w_{q + 1,1}, w_{q + 1,2}\} \cup \{a\}$。字符串 $s^+ = w_{0,1}w_{0,2}w_{1,1}w_{1,2} \ldots w_{q,1}w_{q,2}w_{q + 1,1}w_{q + 1,2}a$，文本 $T$ 是由 $k$ 个 $s^+$ 拼接而成，即 $T = \underbrace{s^+ \cdot s^+ \cdots s^+}_{k \text{ 次}}$。输入字符串集合 $S = \{s_{i,j}, s_{j,i} : \{v_i, v_j\} \in E\} \cup \{s_i : v_i \in V\}$。对于边 $\{v_i, v_j\} \in E$，$s_{i,j} = w_{i,2}w_{i,1}w_{i + 1,1}w_{i + 1,2} \ldots w_{q + 1,1}w_{q + 1,2}aw_{0,1}w_{0,2} \ldots w_{j,2}w_{j,1}$，$s_{j,i} = w_{j,2}w_{j,1}w_{j + 1,1}w_{j + 1,2} \ldots w_{q + 1,1}w_{q + 2,2}aw_{0,1}w_{0,2} \ldots w_{i,2}w_{i,1}$；对于顶点 $v_i \in V$，$s_i = w_{0,1}w_{0,2} \ldots w_{i,2}w_{i,1} \ldots w_{q + 1,1}w_{q + 1,2}$。 - **引理 3**：设 $G = (V, E)$ 是最长路径问题的实例，$(S, T)$ 是对应的 SWCS 实例。则： - 从 $G$ 中长度为 $k$ 的简单路径出发，可以在多项式时间内计算出 SWCS 实例 $(S, T)$ 的一个覆盖 $2k - 1$ 个输入字符串的解。 - 从 SWCS 实例 $(S, T)$ 的一个覆盖 $2k - 1$ 个输入字符串的解出发，可以在多项式时间内计算出 $G$ 中长度为 $k$ 的简单路径。 - **定理 2**：除非 $NP \subseteq coNP/Poly$，否则 SWCS 问题不存在多项式核。 ##### 1.2 $\ell$-RCS 问题的核化复杂度 - **实例构造**：设 $G = (V, E)$ 是最长路径问题的实例，其中 $V = \{v_1, \ldots, v_q\}$。定义字母表 $\Sigma = \{w_i : v_i \in V\} \cup \{z\}$，多重集 $M$ 包含每个 $v_i \in V$ 对应的一个 $w_i$ 以及 $k + 1$ 个字符 $z$。输入字符串集合 $S = \{s_{i,j}, s_{j,i} : \{v_i, v_j\} \in E\}$，其中 $s_{i,j} = zw_izw_jz$，$s_{j,i} = zw_jzw_iz$，且 $S$ 中每个输入字符串的长度都不超过 5。 - **引理 4**：设 $G = (V, E)$ 是最长路径问题的实例，$(S, M)$ 是对应的 $\ell$-RCS 实例。则： - 从 $G$ 中长度为 $k$ 的简单路径出发，可以在多项式时间内计算出 $\ell$-RCS 实例 $