平面多割与多项式层次结构实例压缩研究

### 平面多割与多项式层次结构实例压缩研究 #### 平面多割问题 在图论中，平面多割问题是一个重要的研究方向。对于图 $G = (V, E)$，我们有以下相关概念和结论。 ##### 推论 1 设 $C$ 是图 $G$ 中的最小多簇割，$V_i$ 是 $G' = (V, E \setminus C)$ 的一个连通分量，$C_i$ 是 $G^*$ 中相关的曲线，$\omega_1, \ldots, \omega_{q_i}$ 是 $C_i$ 经过的关节点。那么，$C_i$ 是 $G^*$ 中的最短循环，它与 $G^*$ 中经过 $\omega_1, \ldots, \omega_{q_i}$ 的任何循环 $\Gamma$ 同伦，并且使得 $F_i$ 中的面在 $\Gamma$ 内部，而对于每个 $j \neq i$，$F_j$ 中的面在 $\Gamma$ 外部。 证明过程采用反证法。假设 $C_i$ 不是这样的最短循环，那么我们可以用一个经过 $\omega_1, \ldots, \omega_{q_i}$ 的最短循环 $\Gamma^*$ 替换 $C_i$，使得 $F_i$ 中的面在 $\Gamma^*$ 内部，而对于每个 $j \neq i$，$F_j$ 中的面在 $\Gamma^*$ 外部。根据引理 5，$C' = (C \setminus C_i) \cup \Gamma^*$ 也是 $I$ 的一个有效多簇割。而且，$\Gamma^*$ 比 $C_i$ 严格更短（因为根据引理 2 和 3，它们相对于 $F$ 同伦），因此 $C'$ 是比 $C$ 严格更好的解，这产生了矛盾。 ##### 算法方面 我们可以迭代地构造 $C$，具体步骤如下： 1. 首先“猜测”（即枚举）所有的关节点。 2. 依次计算对应于单个闭合曲线的每个 $C_i$。 3. 移除其内部的顶点，然后继续。 为了计算每个 $C_i$，我们需要先“猜测”$C_i$ 经过哪些关节点（根据引理 4，关节点的最大数量是 $2p - 4$，所以猜测它们需要尝试从 $2|V| - 4$ 个顶点中选择最多 $2p - 4$ 个顶点的所有可能方式，这意味着运行时间将取决于 $p$），然后应用推论 1 找到与 $G^*$ 中某个预定义曲线同伦的最短循环。 我们还需要解决两个问题：一是确保计算的最短循环或路径经过预定的关节点；二是能够生成计算的最短路径可以同伦的所有可能的预定义曲线。具体策略如下： 当 $C_i$ 经过一个给定的关节点时，与该关节点相关的原始面的一些顶点属于 $V_i$。在与 $C_i$ 经过的关节点相关的每个面上，最多有 $h_i + 1$ 组连续顶点（称为区间）属于 $V_i$，其中 $h_i \leq p$ 是 $C_i$ 的内部区域的数量。因此，与给定 $C_i$ 相关的关节点对应于 $V_i$ 中位于与这些关节点相关的原始面上的不同顶点集 $B_i$。对 $B_i$ 进行编码的最佳方法是包含每个区间的两个顶点。 对于平面最小多簇割（MinMCC）问题，我们的算法如下： 1. 对于终端的每个可能聚类，对于 $C_i$ 之间的每个可能包含集，对于关节点的每个可能组合，以及对于 $B_i$ 的每个可能选择： - 计算 $p$ 个不相交的树，每个树跨越某个 $i$ 的 $T_i$ 和 $B_i$，并通过移除第 $i$ 棵树中恰好有一个端点的每条边来构造曲线 $C_i'$。 - 对于除最后一个之外的每个 $i$（按照当前包含集给出的顺序，从不包含其他 $j \neq i$ 的 $C_j$ 的 $C_i$ 开始），计算相对于 $F$ 和 $\bigcup_{j} B_j$ 与 $C_i'$ 同伦的最短循环，然后移除 $G$ 中位于该循环内部的连通分量的顶点。 2. 输出找到的最佳可行解。 该算法的所有步骤都可以在多项式时间内运行，并且可以证明该算法是正确的。由此可得定理：如果簇的大小之和固定，则在平面图中可以在多项式时间内解决 MinMCC 问题。进而得出推论：如果源 - 汇对的数量固定，则在平面图中可以在多项式时间内解决最小割（MinMC）问题。 下面是该算法的流程图： ```mermaid graph TD; A[开始] --> B[枚举终端聚类、包含集、关节点组合和B_i选择]; B --> C[计算p个不相交的树并构造曲线C_i']; C --> D[计算同伦最短循环并移除内部顶点]; D --> E{是否完成所有选择}; E -- 否 --> B; E -- 是 --> F[输出最佳可行解]; F --> G[结束]; ``` #### 多项式层次结构及超越的实例压缩 在复杂性理论中，实例压缩是一个重要的概念。我们将实例可压缩性的概念扩展到多项式层次结构（PH）和 PSPACE 中的参数问题。 ##### 相关定义 - **参数问题**：参数问题是 $\{\langle x, 1^n \rangle | x \in \{0, 1\}^*, n \in \mathbb{N}\}$ 的一个子集，其中 $n$ 称为问题的参数。 - **NP 中的参数