边缘支配集与参数化最大可满足性问题的算法优化

### 边缘支配集与参数化最大可满足性问题的算法优化 #### 边缘支配集问题的参数化近似算法 边缘支配集问题在图论和算法设计领域具有重要地位。对于 $k$-边缘支配集问题，存在一个 $(1 + ρ)$-近似算法，其运行时间为 $O^*(2^{(2 - ρ)k})$（$0 ≤ ρ ≤ 1$）。不过，当 $ρ = 0$ 时，该算法的时间复杂度为 $O^*(4^k)$，与当前最佳的参数化算法运行时间 $O^*(2.3147k)$ 有较大差距。 为了缩小这一差距，我们需要改进参数化近似方案的运行时间。在之前的算法中，为了搜索顶点集 $V_1$，可能需要对每条边进行分支操作。减少分支数量是降低运行时间的一种有效方法，这种方法在精确的固定参数可处理（FPT）算法中已被用于获得更好的运行时间。 ##### 受限边缘支配集的近似算法 考虑一个图 $G = (V, E)$，将顶点集 $V$ 划分为 $(V_1, V_2, V_3)$，满足以下条件： - 诱导图 $G[V_2]$ 的每个连通分量都是一个团。 - $V_2$ 中的顶点和 $V_3$ 中的顶点之间没有边。 给定集合 $V_1$ 后，可以在线性时间内找到 $G[V - V_1]$ 中构成团的连通分量，这些分量构成 $V_2$。 设 $M^*$ 是 $(G = (V, E), V_1)$ 的最小受限边缘支配集，$ν = |M^*|$。用 $α_1$、$α_2$、$α_3$ 分别表示 $M^*$ 中两个端点都在 $V_1 ∪ V_2$、一个端点在 $V_1$ 另一个端点在 $V_3$、两个端点都在 $V_3$ 的边的数量，那么 $ν = α_1 + α_2 + α_3$。 以下是 ApproxPoly1 算法： ```plaintext 输入: 具有上述顶点划分的图 G = (V = V1 ∪ V2 ∪ V3, E) 输出: 一个边缘支配集 M，使得 V1 ⊆ V(M) 1. 向 G[V2] 的每个团 Ci 中添加一个顶点 c′i，创建一个大小为 |Ci| + 1 的团。令 V′2 = {c′1, · · ·, c′p} 为添加的顶点集。 2. 计算 G[V1 ∪ V2 ∪ V′2] 中的最大匹配 M1。 3. 当 M1 中存在边 e = (u, c′i)（c′i ∈ V′2）且 u 存在未被 M1 饱和的邻居 w 时，将 M1 中的 e 替换为 (u, w)。 4. 令 M′1 为 M1 中一个端点在 V′2 的边的集合。 5. 计算 G[V3] 中的最大匹配 M2。 6. 对于 V1 中每个未饱和的顶点，选择一条与之关联的任意边。令 M3 为这些边的集合。 7. 输出 M = M1 ∪ M2 ∪ M3 - M′1。 ``` 引理 3 表明，边缘集 $M = ApproxPoly1(G)$ 是 $(G, V_1)$ 的受限边缘支配集，且 $|M| ≤ (2 - ρ_1)ν$，其中 $ρ_1ν = α_1$ 是 $M^*$ 中两个端点都在 $V_1 ∪ V_2$ 的边的数量。 为了进一步改进参数化近似方案的运行时间，还考虑了一种特殊情况，即划分 $(V_1, V_2, V_3)$ 中 $G[V_3]$ 的每个连通分量都是长度为 2 的路径。设 $N$ 是 $G[V_3]$ 中这些路径的数量，对于最小受限边缘支配集 $M^*$，定义： - $N_1$：$G[V_3]$ 中存在 $M^*$ 中的边连接 $V_1$ 中的顶点和路径中心顶点的路径集合，$n_1 = |N_1|$。 - $N_2$：$G[V_3]$ 中路径本身存在 $M^*$ 中的边的路径集合，$n_2 = |N_2|$。 - $N_3$：$G[V_3]$ 中剩余路径的集合，$n_3 = |N_3|$。 注意，$G[V_3]$ 中的一些路径可能在 $N_1$ 和 $N_2$ 中被重复计数，所以 $N ≤ n_1 + n_2 + n_3$。对于 $n_3$ 中的每条剩余路径，$M^*$ 必须取两条边（$V_1$ 与路径端点之间的边）来覆盖该路径的边，即 $α_2 ≥ 2n_3 + n_1$，且 $n_2 = α_3$。 以下是 ApproxPoly2 算法： ```plaintext 输入: 图 G = (V = V1 ∪ V2 ∪ V3, E)，其中 G[V3] 的每个分量都是长度为 2 的路径 输出: 一个边缘支配集 M，使得 V1 ⊆ V(M) 1. 向 G[V2] 的每个团 Ci 中添加一个顶点 c′i，创建一个大小为 |Ci| + 1 的团。令 V′2 = {c′1, · · ·, c′p} 为添加的顶点集。 2. 计算 G[V1 ∪ V2 ∪ V′2 ∪ V′3] 中的最大匹配 M1，其中 V′3 是 G[V3] 中路径的中心顶点集。 3. 当 M1 中存在边 e = (u, c′i)（c′i ∈ V′2）且 u 存在未被 M1 饱和的邻居 w 时，将 M1 中的 e 替换为 (u, w)。 4. 令 M′1 为 M1 中一个端点在 V′2 的边的集合。 5. 对于中心顶点未被 M1 饱和的每条路径，取该路径中的一条边。令 M2 为这些边的集合。 6. 对于 V1 中每个未饱和的顶点，选择一条任意边。令 M3 为这些边的集合。 7. 输出 M = M1 ∪ M2 ∪ M3 - M′1。 ``` 引理 4 指出，边缘集 $M = ApproxPoly2(G)$ 是 $(G, V_1)$ 的受限边缘支配集，且 $|M| ≤ ν + n_3$。 ##### 改进的参数化近似方案 现在可以给出用于 $k$-边缘支配集和 $k$-受限边缘支配集的改进参数化近似方案 ApproxFPT。其原理是使用一些“好的”分支操作来搜索顶点集 $V_1$，然后在搜索树的每个叶子节点