更快求解最大诱导退化子图问题

### 更快求解最大诱导退化子图问题 #### 1. 退化图的基本概念 对于整数 $d \geq 0$，如果图 $G$ 的每个子图（等价地，每个诱导子图）都包含一个度数至多为 $d$ 的顶点，那么称图 $G$ 是 $d$-退化的。显然，$d$-退化图类在取子图和诱导子图时是封闭的。以下是一些特殊情况： - $0$-退化图是独立集。 - $1$-退化图的类恰好是森林的类。 - 所有平面图都是 $5$-退化的。 - 每个 $K_r$-子式-free 图（特别是，对于 $|V(H)| = r$ 的任何 $H$-子式-free 图）是 $O(r\sqrt{\log r})$-退化的。 有两个关于 $d$-退化图的重要命题： - **命题 4**：设 $G$ 是一个图，$v$ 是 $G$ 中度数至多为 $d$ 的顶点。则 $G$ 是 $d$-退化的当且仅当 $G \setminus v$ 是 $d$-退化的。这一命题表明可以通过依次找到度数至多为 $d$ 的顶点并删除它来测试图的 $d$-退化性。如果能以这种方式移除图的所有顶点，那么该图显然是 $d$-退化的；否则，会得到一个最小度数至少为 $d + 1$ 的诱导子图，这足以证明该图不是 $d$-退化的。此过程可以在多项式时间内实现。 - **命题 5**：任何 $n$ 个顶点的 $d$-退化图最多有 $dn$ 条边。因为在每次删除顶点时，最多从图中移除 $d$ 条边，所以该命题很容易理解。 #### 2. 算法介绍 算法的目标是找到一个 $n$ 顶点图 $G$ 中诱导 $d$-退化图的包含意义下的最大集合 $X$。算法的行为依赖于几个可能依赖于 $d$ 的常数，这些常数的值会影响最终的成功概率。算法维护两个不相交的集合 $A, Z \subseteq V(G)$，分别表示已经确定包含在 $X$ 中的顶点集合和确定不在 $X$ 中的顶点集合。设 $Q = V(G) \setminus (A \cup Z)$ 是尚未确定分配的顶点集合。 算法从 $A = Z = \emptyset$ 开始，由一系列规则组成，在每一步，使用编号最小的适用规则。当应用规则时，根据一些随机决策将 $Q$ 中的一些顶点分配到集合 $A$ 或 $Z$。如果在应用规则之前有 $A \subseteq X$ 且 $Z \cap X = \emptyset$，并且分配到 $A$ 的顶点属于 $X$，分配到 $Z$ 的顶点属于 $V(G) \setminus X$，则称该规则的应用是正确的。 以下是具体的规则： 1. **规则 1**：如果 $|E(G[Q])| \geq \lambda d|Q|$（其中 $\lambda > 4$ 是一个常数），则： - 从 $E(G[Q])$ 中均匀随机选择一条边 $uv$。 - 以概率 $\frac{1}{3}$ 分别做出以下三种决策之一：将 $u$ 分配到 $A$ 并将 $v$ 分配到 $Z$；将 $u$ 分配到 $Z$ 并将 $v$ 分配到 $A$；将 $u$ 和 $v$ 都分配到 $Z$。 - **引理 6**：假设在应用规则 1 之前有 $A \subseteq X$ 且 $Z \cap X = \emptyset$，则规则 1 的应用正确的概率至少为 $\frac{\lambda - 1}{3\lambda}$。 2. **规则 2**：假设存在一个顶点 $v \in Q$ 使得 $|N_G(v) \cap Q| < \kappa d$ 且 $|N_G(v) \cap A| \leq d$（其中 $\kappa > 2\lambda$ 是一个常数）。设 $r = |N_G(v) \cap Q|$，$v_1, v_2, \ldots, v_r$ 是 $v$ 在 $Q$ 中的邻居的任意排序。设 $\gamma = \gamma(r) \geq 1$ 满足 $\gamma^{-1} + \gamma^{-2} + \ldots + \gamma^{-r - 1} = 1$。随机做出以下决策之一： - 对于 $1 \leq i \leq r$，以概率 $\gamma^{-i}$ 将 $v_1, v_2, \ldots, v_{i - 1}$ 分配到 $Z$ 并将 $v_i$ 分配到 $A$。 - 以概率 $\gamma^{-r - 1}$ 将所有顶点 $v_1, v_2, \ldots, v_r$ 分配到 $Z$ 并将 $v$ 分配到 $A$。 - **引理 7**：假设在应用规则 2 之前有 $A \subseteq X$ 且 $Z \cap X = \emptyset$，则规则 2 中考虑的决策中恰好有一个会导致正确的应用。而且，如果在正确的决策中恰好有 $i_0$ 个顶点被分配到 $A \cup Z$，则选择正确决策的概率等于 $\gamma^{-i_0}$。 3. **规则 3**：如果 $Q$ 中至少有 $cd|A|$ 个顶点在 $A$ 中有超过 $d$ 个邻居（其中 $c > 2$ 是一个常数），则从这些顶点中均匀随机选择一个并将其分配到 $Z$。 - **引理 8**：假设在应用规则 3 之前有 $A \subseteq X$ 且 $Z \cap X = \emptyset$，则规则 3 的应用正确的概率至少为 $1 - \frac{1}{c}$。 以下是这些规则的流程图： ```mermaid graph TD A[开始] --> B{是否满足规则1条件} B -- 是 --> C[应用规则1] B -- 否 --> D{是否满足规则2条件} D -- 是 --> E[应用规则2] D -- 否 --> F{是否满足规则3条件} F -- 是 --> G[应用规则3] F -- 否 --> H[规则1,2,3均不适用] ``` #### 3. 常数取值示例 对于不同的 $d$ 值，以下是一些常数的取值示例以及对应的成功概率： | $d$ | $\lambda$ | $\kappa$ | $c$ | $\alpha$ | $2 - \varepsilon_d$ | | --- | --- | --- | --- | --- | --- | | 1 | 4.0238224 | 9 | 2.00197442 | 0.050203 | 1.99991 | | 2 | 4.00009156 | 17/2 | 2.00000763 | 0.01449 | 1.9999999 | | 3 | 4.000000357628 | 25/3 | 2.0000000298 | 0.0066225 | 1.9999999999 | | 4 | 4.000000001397 | 33/4 | 2.0000000001164 | 0.0037736 | 1.9999999999996 | | 5 | 4.000000000005457 | 41/5 | 2.0000000000004548 | 0.0024331 | 1.999999999999999 | | 6 | 4.000000000000021316 | 49/6 | 2.0000000000000017833 | 0.0016978 | 1.999999999999999997 | ### 更快求解最大诱导退化子图问题 #### 4. 规则不适用时的情况 当规则 1、2 和 3 都不适用时，有以下重要结论： - **引理 9**：如果规则 1、2 和 3 都不适用，那么 $|A \cup Z| > \alpha n$，其中 $\alpha > 0$ 是一个仅依赖于常数 $d$、$\lambda$、$\kappa$ 和 $c$ 的常数。 - 证明思路：因为规则 1 不适用，所以 $Q$ 中度数至少为 $\kappa d$ 的顶点至多有 $\frac{2\lambda}{\kappa}|Q|$ 个。又因为规则 2 不适用，所以剩下的顶点在 $A$ 中的邻居数超过 $d$ 个。再由于规则 3 不适用，可得 $\frac{\kappa - 2\lambda}{\kappa}|Q| < cd|A| \leq cd|A \cup Z|$。因为 $Q = V(G) \setminus (A \cup Z)$，经过简单计算可知这等价于 $\frac{|A \cup Z|}{|V(G)|} > (\frac{cd\kappa}{\kappa - 2\lambda + 1})^{-1}$，从而完成证明。 这表明当规则 1、2 和 3 都无法应用时，算法已经对图中相当一部分顶点做出了决策。 #### 5. 算法的收尾规则 当 $|A \cup Z| > \alpha n$（$\alpha$ 由引理 9 给出）时，使用规则 4 来完成算法： - **规则 4**：对于每个 $v \in Q$，独立地以概率 $\frac{1}{2}$ 将 $v$ 分配到 $A$ 或 $Z$。如果 $A$ 诱导出一个 $d$-退化图，则输出集合 $A$；否则，报告错误。 #### 6. 成功概率分析 - **引理 10**：算法输出集合 $X$ 的概率至少为 $\max\{(\frac{3\lambda}{\lambda - 1}), \gamma(\lceil\kappa d\rceil - 1), \frac{c}{c - 1}\}^{-\alpha n}2^{-(1 - \alpha)n}$，这等于 $(2 - \varepsilon_d)^n$，其中 $\varepsilon_d > 0$。 - 证明思路：根据常数的选择和引理 9 可知，$\frac{3\lambda}{\lambda - 1} < 4$，$\gamma(\lceil\kappa d\rceil - 1) < 2$，$\frac{c}{c - 1} < 2$ 且 $\alpha > 0$。所以，只需证明在应用规则 4 之前，$A \subseteq X$ 且 $Z \cap X = \emptyset$ 的概率至少为 $\max\{(\frac{3\lambda}{\lambda - 1}), \gamma(\lceil\kappa d\rceil - 1), \frac{c}{c - 1}\}^{-|A\cup Z|}$，而这是引理 6、7 和 8 的直接推论。 以下是整个算法流程的详细流程图： ```mermaid graph TD A[开始] --> B{是否满足规则1条件} B -- 是 --> C[应用规则1] C --> B B -- 否 --> D{是否满足规则2条件} D -- 是 --> E[应用规则2] E --> B D -- 否 --> F{是否满足规则3条件} F -- 是 --> G[应用规则3] G --> B F -- 否 --> H{是否|A ∪ Z| > αn} H -- 是 --> I[应用规则4] H -- 否 --> B I --> J{输出A是否为d - 退化图} J -- 是 --> K[输出集合A] J -- 否 --> L[报告错误] ``` #### 7. 后续思考与展望 虽然已经证明了可以在 $(2 - \varepsilon_d)^n n^{O(1)}$ 时间内解决最大 $d$-退化诱导子图问题，但仍有一些值得深入探讨的问题： - **算法去随机化**：规则 2 和 3 可以很容易地转化为适当的分支规则，但目前还不清楚如何在不使用随机化的情况下处理规则 1。 - **运行时间优化**：当前算法的常数 $\varepsilon_d$ 即使对于较小的 $d$ 值也非常小，主要原因有两个：规则 2 相对于直接的暴力算法的改进非常小（即 $\gamma(\lfloor\kappa d\rfloor)$ 非常接近 2），并且算法在处理完图的一小部分 $\alpha$ 后就退回到规则 4。能否显著提高算法的运行时间是一个值得研究的问题。 - **通用常数问题**：是否存在一个与 $d$ 无关的通用常数 $\varepsilon$，使得最大 $d$-退化诱导子图问题可以在 $(2 - \varepsilon)^n n^{O(1)}$ 时间内解决，这也是一个有趣的研究方向。 - **更广泛的图类问题**：对于多项式可识别的有界退化图类 $\mathcal{G}$（即存在常数 $d$ 使得每个 $G \in \mathcal{G}$ 都是 $d$-退化的），能否在 $(2 - \varepsilon_{\mathcal{G}})^n$ 时间内解决相应的最大诱导 $\mathcal{G}$-子图问题，以及是否可以为这类问题证明一些元结果，都是极具挑战性的目标。需要注意的是，规则 1 和 3 对于任何这样的图类 $\mathcal{G}$ 都是有效的，但规则 2 中的贪心步骤并不一定适用，即使输入图被假设为 $d$-退化的，目前也不清楚如何比 $2^n$ 更快地解决最大诱导 $\mathcal{G}$-子图问题。 综上所述，求解最大诱导退化子图问题虽然已经取得了一定的进展，但仍有许多问题等待进一步的研究和解决。通过不断优化算法和探索新的方法，有望在这个领域取得更显著的成果。