基于线性规划的图最小边控制集问题的原始-对偶近似算法求解示例

字数 15548 2025-12-17 18:48:07

基于线性规划的图最小边控制集问题的原始-对偶近似算法求解示例

问题描述

考虑一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。一个边子集 \(D \subseteq E\) 称为边控制集，如果对于图中的每一条边 \(e \in E\)，要么 \(e \in D\)，要么存在一条边 \(f \in D\) 与 \(e\) 至少共享一个公共顶点。换句话说，每条边要么在 \(D\) 中，要么至少与 \(D\) 中的一条边相邻（即有一条公共顶点）。最小边控制集问题是寻找一个包含最少边数的边控制集。这是一个NP难问题。本示例将展示如何将其建模为整数线性规划，设计其线性规划松弛，并利用原始-对偶框架设计一个2-近似算法。

第一步：整数线性规划建模

设决策变量 \(x_e \in \{0,1\}\) 表示边 \(e\) 是否被选入边控制集 \(D\) 中（\(x_e = 1\) 表示选中）。目标是最小化选中边的数量。约束条件：对于每条边 \(e \in E\)，它要么自身被选中，要么至少有一条与其相邻的边被选中。因此，对每条边 \(e\)，其相邻边集合记为 \(N(e) = \{ f \in E \mid e \cap f \neq \emptyset \}\)，即与 \(e\) 至少共享一个顶点的边集合。约束可写为：

\[\sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \]

因为 \(e\) 自身也属于 \(N(e)\)，所以这个约束保证了每条边要么自己覆盖自己，要么被相邻边覆盖。于是整数规划为：

\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \\ & x_e \in \{0,1\}, \quad \forall e \in E \end{aligned} \]

第二步：线性规划松弛与对偶

将整数变量松弛为连续变量，得到线性规划松弛：

\[\begin{aligned} \text{(P)} \quad \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \\ & x_e \ge 0, \quad \forall e \in E \end{aligned} \]

其对偶线性规划为：

\[\begin{aligned} \text{(D)} \quad \max \quad & \sum_{e \in E} y_e \\ \text{s.t.} \quad & \sum_{e: f \in N(e)} y_e \le 1, \quad \forall f \in E \\ & y_e \ge 0, \quad \forall e \in E \end{aligned} \]

对偶变量 \(y_e\) 对应于每条边 \(e\)。对偶约束的含义是：对于每条边 \(f\)，所有与其相邻的边 \(e\)（包括 \(f\) 自己）的对偶变量之和不超过1。

第三步：原始-对偶近似算法设计

原始-对偶方法通常从对偶可行解出发，通过互补松弛条件指导构造原始整数解。我们采用以下步骤设计一个2-近似算法：

初始化：设所有原始变量 \(x_e = 0\)，所有对偶变量 \(y_e = 0\)，边集合 \(D = \emptyset\)。
逐步增加对偶变量：同时增加所有未被覆盖的边（即满足 \(\sum_{f \in N(e)} x_f = 0\) 的边 \(e\)）的对偶变量 \(y_e\)，直到某条边 \(f\) 的对偶约束变为紧（即 \(\sum_{e: f \in N(e)} y_e = 1\)）。当一条边 \(f\) 的对偶约束变为紧时，将 \(f\) 加入 \(D\)（即设 \(x_f = 1\)）。由于加入 \(f\) 会覆盖所有与 \(f\) 相邻的边，将这些边标记为已覆盖。
重复步骤2，直到所有边都被覆盖。
返回 \(D\) 作为近似解。

算法中“同时增加”意味着每次迭代中，所有未被覆盖的边 \(e\) 的 \(y_e\) 同步增加一个相同的量 \(\delta\)，直到某个对偶约束达到等式。这个过程可以通过模拟实现，无需显式求解线性规划。

第四步：算法正确性分析

在每一步，当一条边 \(f\) 的对偶约束变为紧时，我们将其加入 \(D\)。由于 \(f\) 覆盖自身及所有与其相邻的边，这些边会被标记为覆盖。因此，算法终止时，所有边都被覆盖，\(D\) 是一个边控制集。
原始目标值 \(|D| = \sum_{e \in D} 1\)。对偶目标值 \(\sum_{e \in E} y_e\)。由于对偶约束 \(\sum_{e: f \in N(e)} y_e \le 1\)，每条被选中的边 \(f \in D\) 对应一个紧约束，即 \(\sum_{e: f \in N(e)} y_e = 1\)。

第五步：近似比证明

考虑最终的 \(D\) 和对偶解 \(y\)。每条边 \(e \in E\) 最多被两条 \(D\) 中的边覆盖？不对，实际上一条边可能被多条 \(D\) 中的边覆盖。我们需要更精细的估计。

观察：对于每条被选中的边 \(f \in D\)，其相邻边集合 \(N(f)\) 中所有边的对偶变量之和为1（因为约束是紧的）。但是，一条边 \(e\) 可能出现在多个这样的相邻集合中。不过，我们可以利用对偶可行性来推导上界。

对原始目标值：

\[|D| = \sum_{f \in D} 1 = \sum_{f \in D} \left( \sum_{e: f \in N(e)} y_e \right) \]

因为对每条 \(f \in D\)，有 \(\sum_{e: f \in N(e)} y_e = 1\)。

交换求和次序：

\[|D| = \sum_{e \in E} y_e \cdot |\{ f \in D \mid f \in N(e) \}| \]

这里 \(|\{ f \in D \mid f \in N(e) \}|\) 是 \(D\) 中与边 \(e\) 相邻的边数。对于任意边 \(e\)，算法中当 \(e\) 第一次被覆盖时，我们选择了某条边 \(f\) 加入 \(D\) 来覆盖 \(e\)。之后 \(e\) 可能被其他后续加入的边再次覆盖。但注意，一旦 \(e\) 被覆盖，其 \(y_e\) 就不再增加。因此，在 \(e\) 的 \(y_e\) 停止增加的时刻，只有一条边（即覆盖 \(e\) 的那条边）在 \(D\) 中与 \(e\) 相邻。然而，后续可能还有其他边加入 \(D\) 也与 \(e\) 相邻，但这些边不会影响 \(y_e\) 的值。所以，对每条边 \(e\)，最多有两条 \(D\) 中的边与其相邻？实际上，考虑一个三角形图（三条边两两相邻），算法可能选择三条边中的两条，则另一条边与两条选中边相邻。但更坏的情况是，一条边可能与多个选中边相邻。我们需要一个上界。

关键观察：对偶约束 \(\sum_{e: f \in N(e)} y_e \le 1\) 意味着每条边 \(f\) 的“对偶负担”最多为1。由于每条边 \(e\) 最多与 \(\Delta'\) 条边相邻，其中 \(\Delta'\) 是边图的度？但这不是我们想要的。

更直接的方法：由于对每条选中的边 \(f\)，其紧约束涉及 \(y_e\) 对相邻边 \(e\) 的贡献，而每条边 \(e\) 的对偶变量 \(y_e\) 在最终对偶解中被考虑了多次，但每次对应一个不同的 \(f\)。实际上，我们可以证明 \(|\{ f \in D \mid f \in N(e) \}| \le 2\) 对于任意 \(e\) 成立吗？不一定。考虑一个星形图，中心顶点连接 \(k\) 个叶子，边集合为 \(\{e_1, e_2, \dots, e_k\}\) 都相邻。算法可能选择所有 \(k\) 条边，则每条边与其他 \(k-1\) 条边相邻，即 \(|\{ f \in D \mid f \in N(e) \}| = k-1\)，可以很大。因此，我们需要另一种分析技巧。

标准原始-对偶分析通常利用互补松弛条件的近似版本。我们证明近似比2。

设 \(D\) 是算法输出的边控制集。对每条边 \(e \in E\)，定义它在算法过程中被覆盖的时间（即其 \(y_e\) 停止增加的时刻）为 \(t_e\)。设 \(f_e\) 是在时刻 \(t_e\) 加入 \(D\) 的边（即覆盖 \(e\) 的边）。注意 \(f_e\) 与 \(e\) 相邻（或相同）。则对每条选中的边 \(f \in D\)，考虑所有满足 \(f_e = f\) 的边 \(e\) 的集合 \(S_f\)。由算法，当 \(f\) 加入时，它覆盖了所有当时未被覆盖且与 \(f\) 相邻的边，因此 \(S_f\) 包含 \(f\) 自身以及所有在那一刻与 \(f\) 相邻且未被覆盖的边。由于 \(f\) 的加入，这些边都被覆盖，且之后不会再被考虑。所以集合 \(\{S_f\}_{f \in D}\) 是 \(E\) 的一个划分（每条边 \(e\) 属于恰好一个 \(S_f\)）。

现在，原始目标值 \(|D| = \sum_{f \in D} 1\)。对偶目标值 \(\sum_{e \in E} y_e = \sum_{f \in D} \sum_{e \in S_f} y_e\)。由于在时刻 \(t_e\)，边 \(f\) 的对偶约束变为紧，即 \(\sum_{e: f \in N(e)} y_e = 1\)。但注意 \(S_f \subseteq \{ e \in E \mid f \in N(e) \}\)，因为 \(S_f\) 中的边要么是 \(f\) 自身，要么与 \(f\) 相邻。所以 \(\sum_{e \in S_f} y_e \le \sum_{e: f \in N(e)} y_e = 1\)。因此，对偶目标值 \(\sum_{e \in E} y_e \le \sum_{f \in D} 1 = |D|\)。

由弱对偶定理，线性规划松弛 (P) 的最优值 \(OPT_{LP} \ge \sum_{e \in E} y_e\)。而整数最优解 \(OPT \ge OPT_{LP}\)。所以 \(|D| = \sum_{f \in D} 1 \ge \sum_{e \in E} y_e \le OPT\)? 这给出了下界，但我们需要上界。

实际上，我们可以证明 \(|D| \le 2 \sum_{e \in E} y_e\)。因为对每个 \(f \in D\)，其紧约束 \(\sum_{e: f \in N(e)} y_e = 1\)。每条边 \(e\) 最多出现在两个这样的集合中？为什么？因为一条边 \(e\) 有两个端点，每个端点关联的边中最多有一条被选入 \(D\)？不一定，一个端点可能关联多条选中边。但注意，当算法选择一条边 \(f\) 时，它覆盖了所有与 \(f\) 相邻的边，包括那些共享一个或两个端点的边。之后，这些被覆盖的边不会再导致其他边被选择。因此，每条边 \(e\) 最多贡献给两个不同的 \(f\) 的紧约束？更严谨地，考虑边 \(e = (u,v)\)。如果 \(e\) 自身被选中，则它只出现在自己的紧约束中。如果 \(e\) 未被选中，则它被某条相邻边覆盖，设为 \(f_1\) 覆盖了端点 \(u\)，\(f_2\) 覆盖了端点 \(v\)？但算法中，覆盖一条边只需要一条选中边，所以 \(e\) 只被一条边覆盖。那么 \(e\) 的 \(y_e\) 只会出现在覆盖它的那条边的紧约束中。因此，每条边 \(e\) 最多出现在一个紧约束的求和中。所以 \(\sum_{f \in D} \sum_{e: f \in N(e)} y_e = \sum_{e \in E} y_e \cdot |\{ f \in D \mid f \in N(e) \}|\)，而 \(|\{ f \in D \mid f \in N(e) \}|\) 是覆盖 \(e\) 的选中边数量，至少为1，但可能大于1吗？如果 \(e\) 被多条选中边覆盖，则大于1。然而，算法中一条边一旦被覆盖，就不再考虑，但后续可能另一条选中边也与其相邻（尽管不会因为覆盖它而被选中）。例如，三角形三边两两相邻，算法可能先选边1，覆盖边2和3；然后边2和3已被覆盖，但算法可能还会选边2吗？不会，因为边2已被覆盖，其 \(y_2\) 不增加，所以不会触发边2的约束变紧。实际上，算法中只有未被覆盖的边的对偶变量增加，所以一条边被覆盖后，不会再导致新的边被选中。因此，每条边 \(e\) 最多被一条选中的边覆盖（在算法中）。所以 \(|\{ f \in D \mid f \in N(e) \}| = 1\) 对每条边 \(e\) 成立。于是：

\[|D| = \sum_{f \in D} 1 = \sum_{f \in D} \sum_{e: f \in N(e)} y_e = \sum_{e \in E} y_e \cdot 1 = \sum_{e \in E} y_e \]

因此原始目标值等于对偶目标值。但这是否意味着算法找到了最优解？不对，因为对偶解 \(y\) 可能不是对偶线性规划 (D) 的最优解，它只是一个可行解。由弱对偶，\(\sum_{e \in E} y_e \le OPT_{LP} \le OPT\)，所以 \(|D| = \sum_{e \in E} y_e \le OPT\)，这给出了下界，但我们需要上界来证明近似比。

矛盾出现了。实际上，我们的算法可能并不总能达到最优。我们需要更仔细的分析。经典结果：最小边控制集问题的原始-对偶算法是2-近似的。让我们重新检查。

整数规划约束：对每条边 \(e\)，\(\sum_{f \in N(e)} x_f \ge 1\)。对偶约束：对每条边 \(f\)，\(\sum_{e: f \in N(e)} y_e \le 1\)。在算法中，当一条边 \(f\) 的约束变紧时，我们设 \(x_f = 1\)。然后，所有满足 \(f \in N(e)\) 的边 \(e\) 都被覆盖，即这些 \(e\) 的约束都满足。但之后，这些 \(e\) 的对偶变量 \(y_e\) 可能还会增加吗？不会，因为一旦一条边被覆盖，其 \(y_e\) 就停止增加。所以每条边 \(e\) 最多对一个 \(f\) 的紧约束有贡献。因此，对每个 \(f \in D\)，有 \(\sum_{e: f \in N(e)} y_e = 1\)，并且这些 \(e\) 的集合是互不相交的（因为每条边 \(e\) 只被一个 \(f\) 覆盖）。所以：

\[|D| = \sum_{f \in D} 1 = \sum_{f \in D} \sum_{e: f \in N(e)} y_e = \sum_{e \in E} y_e \]

于是对偶目标值等于原始解的大小。由弱对偶，\(\sum_{e \in E} y_e \le OPT_{LP} \le OPT\)，所以 \(|D| \le OPT\)? 这意味算法精确最优，但问题NP难，矛盾。

问题出在哪里？错误在于：一条边 \(e\) 可能被多个 \(f \in D\) 覆盖，尽管在算法中它只被一个 \(f\) 首次覆盖，但后续可能有其他 \(f'\) 也被选中且与 \(e\) 相邻，尽管这不是因为覆盖 \(e\) 的需求。例如，考虑一个长度为3的路：边 \(e_1 = (1,2)\), \(e_2 = (2,3)\), \(e_3 = (3,4)\)。算法：初始所有 \(y=0\)。增加 \(y_{e_1}, y_{e_2}, y_{e_3}\) 直到某个约束变紧。边 \(e_2\) 的相邻边是 \(\{e_1, e_2, e_3\}\)，约束为 \(y_{e_1}+y_{e_2}+y_{e_3} \le 1\)。假设我们同时增加它们，当都增加到 \(1/3\) 时，\(e_2\) 的约束变为紧（因为 \(1/3+1/3+1/3=1\)）。于是我们选择 \(e_2\) 加入 \(D\)，覆盖 \(e_1, e_2, e_3\)。所以 \(D=\{e_2\}\)，这是最优解。但如果我们改变顺序，假设先增加 \(y_{e_1}\) 和 \(y_{e_3}\) 更快？不对，算法是同时增加所有未被覆盖的边。但如果我们考虑一个三角形图：三条边两两相邻。同时增加 \(y_1, y_2, y_3\)，当都增加到 \(1/3\) 时，每条边的约束都变成 \(1/3+1/3+1/3=1\)，所以三条边的约束同时变紧。算法可以选择其中一条，比如 \(e_1\)，加入 \(D\)，覆盖 \(e_1, e_2, e_3\)。之后所有边都被覆盖，算法停止，\(D=\{e_1\}\)，这也是最优解。所以在这个例子中，算法确实找到了最优解。但一般情况呢？

考虑一个星形图：中心顶点 \(v\) 连接叶子 \(u_1, u_2, u_3\)，边为 \(e_1=(v,u_1), e_2=(v,u_2), e_3=(v,u_3)\)。这些边两两相邻（因为它们共享顶点 \(v\)）。所以与三角形类似，同时增加 \(y\) 到 \(1/3\)，所有约束变紧，算法选择一条边，比如 \(e_1\)，加入 \(D\)，覆盖所有边，因为 \(e_1\) 与 \(e_2, e_3\) 相邻。所以 \(D=\{e_1\}\)，也是最优解。因此算法似乎总是最优？但最小边控制集问题是NP难的，矛盾。实际上，最小边控制集在一般图中是NP难，但在某些特殊图（如二分图）中是多项式可解的。我们的算法是精确的吗？不，因为对于一般图，整数规划松弛可能有间隙。让我们看一个反例。

考虑一个4个顶点的图：顶点1,2,3,4，边为 (1,2), (2,3), (3,4), (1,4)。这是一个4-cycle。边控制集：可以选择两条对边，比如 (1,2) 和 (3,4)，但这两条边不相邻，所以边 (2,3) 和 (1,4) 没有被控制（因为它们不与选中边相邻）。实际上，这个图的最小边控制集大小为2，例如选择 (1,2) 和 (1,4) 两条相邻边，它们覆盖所有边。但我们的算法：初始所有 \(y=0\)。增加所有边的 \(y\)。每条边有两个相邻边（除了自己）。约束：对边 (1,2)，相邻边为 (1,2), (1,4), (2,3)，所以约束为 \(y_{12}+y_{14}+y_{23} \le 1\)。类似其他边。当所有 \(y\) 增加到 \(1/3\) 时，所有约束都满足（因为每个约束有三项，和为1）。此时所有约束都变紧？检查：对 (1,2)：\(1/3+1/3+1/3=1\)，是紧的。所以算法可能选择一条边，比如 (1,2)，加入 \(D\)，覆盖 (1,2), (1,4), (2,3)。剩下边 (3,4) 未被覆盖（它与 (1,2) 不相邻）。所以继续增加未被覆盖的边 (3,4) 的 \(y_{34}\)，同时可能也增加已被覆盖的边的 \(y\)? 不，已被覆盖的边的 \(y\) 不再增加。所以只增加 \(y_{34}\)。但 (3,4) 的相邻边有 (2,3), (3,4), (1,4)。其中 (2,3) 和 (1,4) 已被覆盖，它们的 \(y\) 不变。约束为 \(y_{23}+y_{34}+y_{14} \le 1\)，当前 \(y_{23}=1/3, y_{14}=1/3, y_{34}=0\)，所以和为 \(2/3\)。增加 \(y_{34}\)，当 \(y_{34}=1/3\) 时，约束变为 \(1/3+1/3+1/3=1\)，变紧，选择 (3,4) 加入 \(D\)。现在 \(D=\{(1,2), (3,4)\}\)。但 (1,2) 和 (3,4) 不相邻，所以边 (2,3) 和 (1,4) 被覆盖了吗？边 (2,3) 与 (1,2) 相邻，所以被覆盖；边 (1,4) 与 (1,2) 相邻，也被覆盖。但边 (1,2) 和 (3,4) 自身被覆盖。所以所有边都被覆盖。解的大小为2，是最优的。所以算法仍然找到了最优解。

这提示：也许最小边控制集的整数规划松弛是精确的？不，因为问题是NP难的，所以整数规划松弛应该有间隙。实际上，考虑一个5个顶点的图：一个三角形 (1,2,3) 加上一个悬挂边 (3,4) 和 (4,5)。边集合：\(e_1=(1,2), e_2=(2,3), e_3=(1,3), e_4=(3,4), e_5=(4,5)\)。整数最优解：可以选择 \(e_2\) 和 \(e_4\)，覆盖所有边。大小2。线性规划松弛：最优解可能赋值 \(x_{e_1}=x_{e_2}=x_{e_3}=0.5, x_{e_4}=1, x_{e_5}=0.5?\) 检查约束：对 \(e_1\)，相邻边为 \(e_1,e_2,e_3\)，和=0.5+0.5+0.5=1.5>1，满足。对 \(e_5\)，相邻边为 \(e_4,e_5\)，和=1+0.5=1.5>1。目标值=0.5+0.5+0.5+1+0.5=3。但整数最优为2，所以有间隙。我们的算法在这个实例上：初始所有 \(y=0\)。增加所有边的 \(y\)。当增加到某个值，假设同时增加，直到某约束变紧。边 \(e_4\) 的相邻边只有 \(e_3,e_4,e_5\)? 实际 \(e_4=(3,4)\)，相邻边有：\(e_2=(2,3)\), \(e_3=(1,3)\), \(e_4\), \(e_5=(4,5)\)。所以约束为 \(y_2+y_3+y_4+y_5 \le 1\)。边 \(e_5\) 相邻边有 \(e_4,e_5\)。当所有 \(y\) 增加到 \(1/4\) 时，边 \(e_4\) 的约束变为 \(4*(1/4)=1\)，变紧。算法选择 \(e_4\) 加入 \(D\)，覆盖 \(e_2,e_3,e_4,e_5\)。剩下 \(e_1\) 未被覆盖（因为 \(e_1\) 与 \(e_4\) 不相邻）。然后增加 \(y_1\)，同时 \(e_1\) 的相邻边有 \(e_1,e_2,e_3\)，其中 \(y_2=y_3=1/4\)，所以当 \(y_1\) 增加到 \(1/2\) 时，约束 \(y_1+y_2+y_3=1/2+1/4+1/4=1\) 变紧，选择 \(e_1\) 加入 \(D\)。最终 \(D=\{e_4,e_1\}\)，大小2，是最优的。所以算法还是找到了最优。

这说明该算法可能总是精确求解？实际上，最小边控制集问题虽然NP难，但其线性规划松弛可能是整数解？不，因为整数规划是覆盖类型，通常有间隙。但经典结论：最小边控制集的原始-对偶算法是2-近似的。我们的分析哪里出错了？我们需要重新审视近似比证明。

标准分析：设算法选中的边集为 \(D\)。对每条边 \(e \in E\)，定义其“见证”边 \(f(e)\) 为算法中覆盖 \(e\) 的边（即当 \(e\) 被覆盖时，加入 \(D\) 的那条边）。注意 \(f(e)\) 与 \(e\) 相邻或相同。则对每条选中的边 \(f \in D\)，考虑集合 \(S_f = \{ e \in E \mid f(e) = f \}\)。显然 \(\{S_f\}_{f \in D}\) 是 \(E\) 的一个划分。由算法，当 \(f\) 被选中时，对所有 \(e \in S_f\)，有 \(y_e\) 相同（因为它们同步增加）？实际上，在 \(f\) 被选中时，所有 \(e \in S_f\) 的 \(y_e\) 都等于当前值，设为 \(\delta_f\)。所以 \(\sum_{e \in S_f} y_e = |S_f| \cdot \delta_f\)。

由于 \(f\) 的约束在选中时变紧：\(\sum_{e: f \in N(e)} y_e = 1\)。注意 \(S_f \subseteq \{ e \mid f \in N(e) \}\)，所以 \(\sum_{e \in S_f} y_e \le 1\)。即 \(|S_f| \cdot \delta_f \le 1\)。

对偶目标值 \(\sum_{e \in E} y_e = \sum_{f \in D} |S_f| \cdot \delta_f \le \sum_{f \in D} 1 = |D|\)。所以 \(|D| \ge \sum_{e} y_e\)。由弱对偶，\(OPT \ge OPT_{LP} \ge \sum_{e} y_e\)，所以 \(|D| \ge OPT\)? 这显然不对。我们实际上需要上界 \(|D| \le \alpha \sum_{e} y_e\)。但这里得到的是下界。

正确分析应该是：由于每条边 \(e\) 最多出现在两个不同的 \(S_f\) 中？因为一条边有两个端点，每个端点最多贡献一个选中边作为见证？考虑边 \(e = (u,v)\)。它被一条选中边 \(f(e)\) 覆盖。如果 \(f(e)\) 与 \(e\) 共享一个端点，那么另一个端点可能被另一条选中边覆盖，但 \(e\) 本身只被 \(f(e)\) 覆盖。所以每条边只出现在一个 \(S_f\) 中。所以 \(\sum_{f} |S_f| = |E|\)。但 \(|D| = \sum_f 1\)。我们需要关联 \(|D|\) 和 \(\sum_f |S_f| \cdot \delta_f\)。

由于 \(\delta_f \le 1/|S_f|\)（因为 \(|S_f| \cdot \delta_f \le 1\)），所以 \(\sum_e y_e = \sum_f |S_f| \cdot \delta_f \le \sum_f 1 = |D|\)。这仍然是下界。

实际上，经典原始-对偶分析通常证明 \(|D| \le 2 \sum_e y_e\)。为了得到这个，我们需要每个 \(|S_f| \ge 2\)？不一定，可能为1。但注意，当 \(|S_f| = 1\) 时，\(\delta_f \le 1\)，但 \(|S_f| \cdot \delta_f = \delta_f \le 1 = 1 \cdot 1\)，所以 \(|D| = \sum_f 1 \ge \sum_f |S_f| \cdot \delta_f = \sum_e y_e\)。所以 \(|D|\) 可能大于对偶和。但我们需要上界。

我们换一个思路。考虑整数规划约束的系数矩阵。约束 \(\sum_{f \in N(e)} x_f \ge 1\) 中，每个变量 \(x_f\) 出现在所有满足 \(f \in N(e)\) 的约束中，即出现在边 \(f\) 自身和所有与 \(f\) 相邻的边的约束中。所以每个变量出现在最多 \(2\Delta-1\) 个约束中？实际上，一条边有两个端点，每个端点度数最多为 \(\Delta\)，所以相邻边最多为 \(2(\Delta-1)\) 条，加上自身，最多 \(2\Delta-1\) 条。但这与近似比无关。

原始-对偶算法的标准分析：设对偶解为 \(y\)，原始解为 \(x\)（整数）。由互补松弛条件：如果 \(x_f > 0\)，则对应对偶约束紧： \(\sum_{e: f \in N(e)} y_e = 1\)。如果 \(y_e > 0\)，则对应原始约束紧： \(\sum_{f \in N(e)} x_f = 1\)？不，原始约束是大于等于，所以当 \(y_e > 0\) 时，只能推出 \(\sum_{f \in N(e)} x_f = 1\) 如果原始解是最优的。但我们的算法并不保证 \(y_e > 0\) 时原始约束紧。然而，在算法中，当 \(y_e > 0\) 时，边 \(e\) 被覆盖，所以 \(\sum_{f \in N(e)} x_f \ge 1\)，但可能大于1。所以只有一半的互补松弛条件满足。

近似比证明通常利用：对每个选中的 \(f\)，有 \(\sum_{e: f \in N(e)} y_e = 1\)。求和得 \(\sum_{f \in D} \sum_{e: f \in N(e)} y_e = |D|\)。交换求和次序：\(\sum_{e \in E} y_e \cdot |\{ f \in D \mid f \in N(e) \}| = |D|\)。由于每条边 \(e\) 可能被多条选中的边覆盖，即 \(|\{ f \in D \mid f \in N(e) \}|\) 可能大于1。但注意，在算法中，一旦一条边被覆盖，它的对偶变量就不再增加，但后续可能还有其他选中边与其相邻。所以 \(|\{ f \in D \mid f \in N(e) \}|\) 可以大于1。最坏情况下，一条边可能与所有选中的边相邻。但我们希望找到一个上界。

考虑一条边 \(e = (u,v)\)。哪些选中边会与 \(e\) 相邻？选中边必须与 \(e\) 共享至少一个顶点。所以只有那些覆盖 \(u\) 或 \(v\) 的边可能与 \(e\) 相邻。但算法中，一个顶点可能被多条选中边关联。然而，我们可以证明：对于每个顶点，最多有两条选中边与其关联？不对。例如星形图，中心顶点关联所有选中边（如果选中多条）。但星形图中算法只选一条边。考虑一个三角形加一条悬挂边：图：三角形 (1,2), (2,3), (1,3)，加上边 (3,4)。算法可能先选 (1,2)，覆盖三角形所有边，然后 (3,4) 未被覆盖，再选 (3,4)。选中边为 (1,2) 和 (3,4)。顶点3关联两条选中边：(1,2) 不与3相邻？(1,2) 与顶点3不相邻。所以顶点3只关联 (3,4)。顶点1关联 (1,2)。所以每个顶点最多关联一条选中边？不一定。考虑一个图：两个三角形共享一条边。顶点集合1,2,3,4，边： (1,2), (2,3), (1,3) 形成一个三角形，另一个三角形 (2,3), (3,4), (2,4)。共享边 (2,3)。算法可能先选 (2,3)，覆盖所有边？(2,3) 覆盖自身，(1,2), (1,3), (2,4), (3,4) 都与 (2,3) 相邻，所以全部覆盖。所以只选一条边。所以算法往往选出很少的边。

实际上，可以证明：算法选出的边构成一个极大匹配？因为每条选中的边会覆盖所有与其相邻的边，所以选中边之间没有公共顶点？如果有公共顶点，那么一条边会覆盖另一条边，但另一条边不会在之后被选中，因为已被覆盖。所以选中边集合是一个匹配。因为如果两条选中边共享一个顶点，那么先选中的那条会覆盖后选中的那条，所以后选中的那条不会被选中。因此，算法选中的边集 \(D\) 是一个匹配。于是，每条边 \(e\) 最多与两条 \(D\) 中的边相邻（每个端点最多关联一条 \(D\) 中的边，因为 \(D\) 是匹配）。所以 \(|\{ f \in D \mid f \in N(e) \}| \le 2\)。于是：

\[|D| = \sum_{e \in E} y_e \cdot |\{ f \in D \mid f \in N(e) \}| \le 2 \sum_{e \in E} y_e \le 2 \cdot OPT_{LP} \le 2 \cdot OPT \]

因此算法是2-近似的。

第六步：算法步骤详述

输入无向图 \(G=(V,E)\)。
初始化：\(x_e = 0\) 对所有 \(e \in E\)；\(y_e = 0\) 对所有 \(e \in E\)；\(D = \emptyset\)；所有边标记为未覆盖。
当存在未覆盖的边时：
- 设 \(U\) 为未覆盖边的集合。
- 同时增加所有 \(e \in U\) 的 \(y_e\)，直到存在某条边 \(f \in E\) 使得对偶约束 \(\sum_{e: f \in N(e)} y_e = 1\) 成立（注意：即使 \(f\) 已覆盖也可能触发？约束对所有边 \(f\) 都检查。但已覆盖的边的 \(y_e\) 不增加，所以其约束不会变紧，除非之前已紧）。
- 将 \(f\) 加入 \(D\)，设 \(x_f = 1\)。
- 将所有满足 \(f \in N(e)\) 的边 \(e\) 标记为已覆盖（即所有与 \(f\) 相邻的边，包括 \(f\) 自身）。
输出 \(D\)。

实现时，不需要真的逐步增加 \(y_e\)，可以通过计算最小增量来模拟。

第七步：举例说明

考虑一个简单图：路径图 \(P_4\)：边依次为 \(e_1=(1,2), e_2=(2,3), e_3=(3,4)\)。

初始所有边未覆盖，\(y_1=y_2=y_3=0\)。
同时增加 \(y_1, y_2, y_3\)。约束：
- 对 \(e_1\): 相邻边 \(e_1, e_2\)，约束 \(y_1+y_2 \le 1\)。
- 对 \(e_2\): 相邻边 \(e_1, e_2, e_3\)，约束 \(y_1+y_2+y_3 \le 1\)。
- 对 \(e_3\): 相邻边 \(e_2, e_3\)，约束 \(y_2+y_3 \le 1\)。
  当增加到 \(y_1=y_2=y_3=1/3\) 时，约束 \(e_2\) 变为紧。选择 \(e_2\) 加入 \(D\)，覆盖 \(e_1, e_2, e_3\)。
所有边被覆盖，算法结束。\(D=\{e_2\}\)，大小1。实际上最小边控制集至少为1，因为一条边可以控制所有边（因为相邻）。所以是最优解。

第八步：总结

本问题通过整数规划建模，利用原始-对偶方法设计了一个近似算法。算法每次选择对偶约束变紧的边加入解，直到所有边被覆盖。由于选中边构成一个匹配，每条边最多与两条选中边相邻，因此近似比为2。该算法简单高效，适用于大规模图的最小边控制集近似求解。

基于线性规划的图最小边控制集问题的原始-对偶近似算法求解示例问题描述考虑一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。一个边子集 \( D \subseteq E \) 称为边控制集，如果对于图中的每一条边 \( e \in E \)，要么 \( e \in D \)，要么存在一条边 \( f \in D \) 与 \( e \) 至少共享一个公共顶点。换句话说，每条边要么在 \( D \) 中，要么至少与 \( D \) 中的一条边相邻（即有一条公共顶点）。最小边控制集问题是寻找一个包含最少边数的边控制集。这是一个NP难问题。本示例将展示如何将其建模为整数线性规划，设计其线性规划松弛，并利用原始-对偶框架设计一个2-近似算法。第一步：整数线性规划建模设决策变量 \( x_ e \in \{0,1\} \) 表示边 \( e \) 是否被选入边控制集 \( D \) 中（\( x_ e = 1 \) 表示选中）。目标是最小化选中边的数量。约束条件：对于每条边 \( e \in E \)，它要么自身被选中，要么至少有一条与其相邻的边被选中。因此，对每条边 \( e \)，其相邻边集合记为 \( N(e) = \{ f \in E \mid e \cap f \neq \emptyset \} \)，即与 \( e \) 至少共享一个顶点的边集合。约束可写为： \[ \sum_ {f \in N(e)} x_ f \ge 1, \quad \forall e \in E \] 因为 \( e \) 自身也属于 \( N(e) \)，所以这个约束保证了每条边要么自己覆盖自己，要么被相邻边覆盖。于是整数规划为： \[ \begin{aligned} \min \quad & \sum_ {e \in E} x_ e \\ \text{s.t.} \quad & \sum_ {f \in N(e)} x_ f \ge 1, \quad \forall e \in E \\ & x_ e \in \{0,1\}, \quad \forall e \in E \end{aligned} \] 第二步：线性规划松弛与对偶将整数变量松弛为连续变量，得到线性规划松弛： \[ \begin{aligned} \text{(P)} \quad \min \quad & \sum_ {e \in E} x_ e \\ \text{s.t.} \quad & \sum_ {f \in N(e)} x_ f \ge 1, \quad \forall e \in E \\ & x_ e \ge 0, \quad \forall e \in E \end{aligned} \] 其对偶线性规划为： \[ \begin{aligned} \text{(D)} \quad \max \quad & \sum_ {e \in E} y_ e \\ \text{s.t.} \quad & \sum_ {e: f \in N(e)} y_ e \le 1, \quad \forall f \in E \\ & y_ e \ge 0, \quad \forall e \in E \end{aligned} \] 对偶变量 \( y_ e \) 对应于每条边 \( e \)。对偶约束的含义是：对于每条边 \( f \)，所有与其相邻的边 \( e \)（包括 \( f \) 自己）的对偶变量之和不超过1。第三步：原始-对偶近似算法设计原始-对偶方法通常从对偶可行解出发，通过互补松弛条件指导构造原始整数解。我们采用以下步骤设计一个2-近似算法：初始化：设所有原始变量 \( x_ e = 0 \)，所有对偶变量 \( y_ e = 0 \)，边集合 \( D = \emptyset \)。逐步增加对偶变量：同时增加所有未被覆盖的边（即满足 \( \sum_ {f \in N(e)} x_ f = 0 \) 的边 \( e \)）的对偶变量 \( y_ e \)，直到某条边 \( f \) 的对偶约束变为紧（即 \( \sum_ {e: f \in N(e)} y_ e = 1 \)）。当一条边 \( f \) 的对偶约束变为紧时，将 \( f \) 加入 \( D \)（即设 \( x_ f = 1 \)）。由于加入 \( f \) 会覆盖所有与 \( f \) 相邻的边，将这些边标记为已覆盖。重复步骤2 ，直到所有边都被覆盖。返回 \( D \) 作为近似解。算法中“同时增加”意味着每次迭代中，所有未被覆盖的边 \( e \) 的 \( y_ e \) 同步增加一个相同的量 \( \delta \)，直到某个对偶约束达到等式。这个过程可以通过模拟实现，无需显式求解线性规划。第四步：算法正确性分析在每一步，当一条边 \( f \) 的对偶约束变为紧时，我们将其加入 \( D \)。由于 \( f \) 覆盖自身及所有与其相邻的边，这些边会被标记为覆盖。因此，算法终止时，所有边都被覆盖，\( D \) 是一个边控制集。原始目标值 \( |D| = \sum_ {e \in D} 1 \)。对偶目标值 \( \sum_ {e \in E} y_ e \)。由于对偶约束 \( \sum_ {e: f \in N(e)} y_ e \le 1 \)，每条被选中的边 \( f \in D \) 对应一个紧约束，即 \( \sum_ {e: f \in N(e)} y_ e = 1 \)。第五步：近似比证明考虑最终的 \( D \) 和对偶解 \( y \)。每条边 \( e \in E \) 最多被两条 \( D \) 中的边覆盖？不对，实际上一条边可能被多条 \( D \) 中的边覆盖。我们需要更精细的估计。观察：对于每条被选中的边 \( f \in D \)，其相邻边集合 \( N(f) \) 中所有边的对偶变量之和为1（因为约束是紧的）。但是，一条边 \( e \) 可能出现在多个这样的相邻集合中。不过，我们可以利用对偶可行性来推导上界。对原始目标值： \[ |D| = \sum_ {f \in D} 1 = \sum_ {f \in D} \left( \sum_ {e: f \in N(e)} y_ e \right) \] 因为对每条 \( f \in D \)，有 \( \sum_ {e: f \in N(e)} y_ e = 1 \)。交换求和次序： \[ |D| = \sum_ {e \in E} y_ e \cdot |\{ f \in D \mid f \in N(e) \}| \] 这里 \( |\{ f \in D \mid f \in N(e) \}| \) 是 \( D \) 中与边 \( e \) 相邻的边数。对于任意边 \( e \)，算法中当 \( e \) 第一次被覆盖时，我们选择了某条边 \( f \) 加入 \( D \) 来覆盖 \( e \)。之后 \( e \) 可能被其他后续加入的边再次覆盖。但注意，一旦 \( e \) 被覆盖，其 \( y_ e \) 就不再增加。因此，在 \( e \) 的 \( y_ e \) 停止增加的时刻，只有一条边（即覆盖 \( e \) 的那条边）在 \( D \) 中与 \( e \) 相邻。然而，后续可能还有其他边加入 \( D \) 也与 \( e \) 相邻，但这些边不会影响 \( y_ e \) 的值。所以，对每条边 \( e \)，最多有两条 \( D \) 中的边与其相邻？实际上，考虑一个三角形图（三条边两两相邻），算法可能选择三条边中的两条，则另一条边与两条选中边相邻。但更坏的情况是，一条边可能与多个选中边相邻。我们需要一个上界。关键观察：对偶约束 \( \sum_ {e: f \in N(e)} y_ e \le 1 \) 意味着每条边 \( f \) 的“对偶负担”最多为1。由于每条边 \( e \) 最多与 \( \Delta' \) 条边相邻，其中 \( \Delta' \) 是边图的度？但这不是我们想要的。更直接的方法：由于对每条选中的边 \( f \)，其紧约束涉及 \( y_ e \) 对相邻边 \( e \) 的贡献，而每条边 \( e \) 的对偶变量 \( y_ e \) 在最终对偶解中被考虑了多次，但每次对应一个不同的 \( f \)。实际上，我们可以证明 \( |\{ f \in D \mid f \in N(e) \}| \le 2 \) 对于任意 \( e \) 成立吗？不一定。考虑一个星形图，中心顶点连接 \( k \) 个叶子，边集合为 \( \{e_ 1, e_ 2, \dots, e_ k\} \) 都相邻。算法可能选择所有 \( k \) 条边，则每条边与其他 \( k-1 \) 条边相邻，即 \( |\{ f \in D \mid f \in N(e) \}| = k-1 \)，可以很大。因此，我们需要另一种分析技巧。标准原始-对偶分析通常利用互补松弛条件的近似版本。我们证明近似比2。设 \( D \) 是算法输出的边控制集。对每条边 \( e \in E \)，定义它在算法过程中被覆盖的时间（即其 \( y_ e \) 停止增加的时刻）为 \( t_ e \)。设 \( f_ e \) 是在时刻 \( t_ e \) 加入 \( D \) 的边（即覆盖 \( e \) 的边）。注意 \( f_ e \) 与 \( e \) 相邻（或相同）。则对每条选中的边 \( f \in D \)，考虑所有满足 \( f_ e = f \) 的边 \( e \) 的集合 \( S_ f \)。由算法，当 \( f \) 加入时，它覆盖了所有当时未被覆盖且与 \( f \) 相邻的边，因此 \( S_ f \) 包含 \( f \) 自身以及所有在那一刻与 \( f \) 相邻且未被覆盖的边。由于 \( f \) 的加入，这些边都被覆盖，且之后不会再被考虑。所以集合 \( \{S_ f\}_ {f \in D} \) 是 \( E \) 的一个划分（每条边 \( e \) 属于恰好一个 \( S_ f \)）。现在，原始目标值 \( |D| = \sum_ {f \in D} 1 \)。对偶目标值 \( \sum_ {e \in E} y_ e = \sum_ {f \in D} \sum_ {e \in S_ f} y_ e \)。由于在时刻 \( t_ e \)，边 \( f \) 的对偶约束变为紧，即 \( \sum_ {e: f \in N(e)} y_ e = 1 \)。但注意 \( S_ f \subseteq \{ e \in E \mid f \in N(e) \} \)，因为 \( S_ f \) 中的边要么是 \( f \) 自身，要么与 \( f \) 相邻。所以 \( \sum_ {e \in S_ f} y_ e \le \sum_ {e: f \in N(e)} y_ e = 1 \)。因此，对偶目标值 \( \sum_ {e \in E} y_ e \le \sum_ {f \in D} 1 = |D| \)。由弱对偶定理，线性规划松弛 (P) 的最优值 \( OPT_ {LP} \ge \sum_ {e \in E} y_ e \)。而整数最优解 \( OPT \ge OPT_ {LP} \)。所以 \( |D| = \sum_ {f \in D} 1 \ge \sum_ {e \in E} y_ e \le OPT \)? 这给出了下界，但我们需要上界。实际上，我们可以证明 \( |D| \le 2 \sum_ {e \in E} y_ e \)。因为对每个 \( f \in D \)，其紧约束 \( \sum_ {e: f \in N(e)} y_ e = 1 \)。每条边 \( e \) 最多出现在两个这样的集合中？为什么？因为一条边 \( e \) 有两个端点，每个端点关联的边中最多有一条被选入 \( D \)？不一定，一个端点可能关联多条选中边。但注意，当算法选择一条边 \( f \) 时，它覆盖了所有与 \( f \) 相邻的边，包括那些共享一个或两个端点的边。之后，这些被覆盖的边不会再导致其他边被选择。因此，每条边 \( e \) 最多贡献给两个不同的 \( f \) 的紧约束？更严谨地，考虑边 \( e = (u,v) \)。如果 \( e \) 自身被选中，则它只出现在自己的紧约束中。如果 \( e \) 未被选中，则它被某条相邻边覆盖，设为 \( f_ 1 \) 覆盖了端点 \( u \)，\( f_ 2 \) 覆盖了端点 \( v \)？但算法中，覆盖一条边只需要一条选中边，所以 \( e \) 只被一条边覆盖。那么 \( e \) 的 \( y_ e \) 只会出现在覆盖它的那条边的紧约束中。因此，每条边 \( e \) 最多出现在一个紧约束的求和中。所以 \( \sum_ {f \in D} \sum_ {e: f \in N(e)} y_ e = \sum_ {e \in E} y_ e \cdot |\{ f \in D \mid f \in N(e) \}| \)，而 \( |\{ f \in D \mid f \in N(e) \}| \) 是覆盖 \( e \) 的选中边数量，至少为1，但可能大于1吗？如果 \( e \) 被多条选中边覆盖，则大于1。然而，算法中一条边一旦被覆盖，就不再考虑，但后续可能另一条选中边也与其相邻（尽管不会因为覆盖它而被选中）。例如，三角形三边两两相邻，算法可能先选边1，覆盖边2和3；然后边2和3已被覆盖，但算法可能还会选边2吗？不会，因为边2已被覆盖，其 \( y_ 2 \) 不增加，所以不会触发边2的约束变紧。实际上，算法中只有未被覆盖的边的对偶变量增加，所以一条边被覆盖后，不会再导致新的边被选中。因此，每条边 \( e \) 最多被一条选中的边覆盖（在算法中）。所以 \( |\{ f \in D \mid f \in N(e) \}| = 1 \) 对每条边 \( e \) 成立。于是： \[ |D| = \sum_ {f \in D} 1 = \sum_ {f \in D} \sum_ {e: f \in N(e)} y_ e = \sum_ {e \in E} y_ e \cdot 1 = \sum_ {e \in E} y_ e \] 因此原始目标值等于对偶目标值。但这是否意味着算法找到了最优解？不对，因为对偶解 \( y \) 可能不是对偶线性规划 (D) 的最优解，它只是一个可行解。由弱对偶，\( \sum_ {e \in E} y_ e \le OPT_ {LP} \le OPT \)，所以 \( |D| = \sum_ {e \in E} y_ e \le OPT \)，这给出了下界，但我们需要上界来证明近似比。矛盾出现了。实际上，我们的算法可能并不总能达到最优。我们需要更仔细的分析。经典结果：最小边控制集问题的原始-对偶算法是2-近似的。让我们重新检查。整数规划约束：对每条边 \( e \)，\( \sum_ {f \in N(e)} x_ f \ge 1 \)。对偶约束：对每条边 \( f \)，\( \sum_ {e: f \in N(e)} y_ e \le 1 \)。在算法中，当一条边 \( f \) 的约束变紧时，我们设 \( x_ f = 1 \)。然后，所有满足 \( f \in N(e) \) 的边 \( e \) 都被覆盖，即这些 \( e \) 的约束都满足。但之后，这些 \( e \) 的对偶变量 \( y_ e \) 可能还会增加吗？不会，因为一旦一条边被覆盖，其 \( y_ e \) 就停止增加。所以每条边 \( e \) 最多对一个 \( f \) 的紧约束有贡献。因此，对每个 \( f \in D \)，有 \( \sum_ {e: f \in N(e)} y_ e = 1 \)，并且这些 \( e \) 的集合是互不相交的（因为每条边 \( e \) 只被一个 \( f \) 覆盖）。所以： \[ |D| = \sum_ {f \in D} 1 = \sum_ {f \in D} \sum_ {e: f \in N(e)} y_ e = \sum_ {e \in E} y_ e \] 于是对偶目标值等于原始解的大小。由弱对偶，\( \sum_ {e \in E} y_ e \le OPT_ {LP} \le OPT \)，所以 \( |D| \le OPT \)? 这意味算法精确最优，但问题NP难，矛盾。问题出在哪里？错误在于：一条边 \( e \) 可能被多个 \( f \in D \) 覆盖，尽管在算法中它只被一个 \( f \) 首次覆盖，但后续可能有其他 \( f' \) 也被选中且与 \( e \) 相邻，尽管这不是因为覆盖 \( e \) 的需求。例如，考虑一个长度为3的路：边 \( e_ 1 = (1,2) \), \( e_ 2 = (2,3) \), \( e_ 3 = (3,4) \)。算法：初始所有 \( y=0 \)。增加 \( y_ {e_ 1}, y_ {e_ 2}, y_ {e_ 3} \) 直到某个约束变紧。边 \( e_ 2 \) 的相邻边是 \( \{e_ 1, e_ 2, e_ 3\} \)，约束为 \( y_ {e_ 1}+y_ {e_ 2}+y_ {e_ 3} \le 1 \)。假设我们同时增加它们，当都增加到 \( 1/3 \) 时，\( e_ 2 \) 的约束变为紧（因为 \( 1/3+1/3+1/3=1 \)）。于是我们选择 \( e_ 2 \) 加入 \( D \)，覆盖 \( e_ 1, e_ 2, e_ 3 \)。所以 \( D=\{e_ 2\} \)，这是最优解。但如果我们改变顺序，假设先增加 \( y_ {e_ 1} \) 和 \( y_ {e_ 3} \) 更快？不对，算法是同时增加所有未被覆盖的边。但如果我们考虑一个三角形图：三条边两两相邻。同时增加 \( y_ 1, y_ 2, y_ 3 \)，当都增加到 \( 1/3 \) 时，每条边的约束都变成 \( 1/3+1/3+1/3=1 \)，所以三条边的约束同时变紧。算法可以选择其中一条，比如 \( e_ 1 \)，加入 \( D \)，覆盖 \( e_ 1, e_ 2, e_ 3 \)。之后所有边都被覆盖，算法停止，\( D=\{e_ 1\} \)，这也是最优解。所以在这个例子中，算法确实找到了最优解。但一般情况呢？考虑一个星形图：中心顶点 \( v \) 连接叶子 \( u_ 1, u_ 2, u_ 3 \)，边为 \( e_ 1=(v,u_ 1), e_ 2=(v,u_ 2), e_ 3=(v,u_ 3) \)。这些边两两相邻（因为它们共享顶点 \( v \)）。所以与三角形类似，同时增加 \( y \) 到 \( 1/3 \)，所有约束变紧，算法选择一条边，比如 \( e_ 1 \)，加入 \( D \)，覆盖所有边，因为 \( e_ 1 \) 与 \( e_ 2, e_ 3 \) 相邻。所以 \( D=\{e_ 1\} \)，也是最优解。因此算法似乎总是最优？但最小边控制集问题是NP难的，矛盾。实际上，最小边控制集在一般图中是NP难，但在某些特殊图（如二分图）中是多项式可解的。我们的算法是精确的吗？不，因为对于一般图，整数规划松弛可能有间隙。让我们看一个反例。考虑一个4个顶点的图：顶点1,2,3,4，边为 (1,2), (2,3), (3,4), (1,4)。这是一个4-cycle。边控制集：可以选择两条对边，比如 (1,2) 和 (3,4)，但这两条边不相邻，所以边 (2,3) 和 (1,4) 没有被控制（因为它们不与选中边相邻）。实际上，这个图的最小边控制集大小为2，例如选择 (1,2) 和 (1,4) 两条相邻边，它们覆盖所有边。但我们的算法：初始所有 \( y=0 \)。增加所有边的 \( y \)。每条边有两个相邻边（除了自己）。约束：对边 (1,2)，相邻边为 (1,2), (1,4), (2,3)，所以约束为 \( y_ {12}+y_ {14}+y_ {23} \le 1 \)。类似其他边。当所有 \( y \) 增加到 \( 1/3 \) 时，所有约束都满足（因为每个约束有三项，和为1）。此时所有约束都变紧？检查：对 (1,2)：\( 1/3+1/3+1/3=1 \)，是紧的。所以算法可能选择一条边，比如 (1,2)，加入 \( D \)，覆盖 (1,2), (1,4), (2,3)。剩下边 (3,4) 未被覆盖（它与 (1,2) 不相邻）。所以继续增加未被覆盖的边 (3,4) 的 \( y_ {34} \)，同时可能也增加已被覆盖的边的 \( y \)? 不，已被覆盖的边的 \( y \) 不再增加。所以只增加 \( y_ {34} \)。但 (3,4) 的相邻边有 (2,3), (3,4), (1,4)。其中 (2,3) 和 (1,4) 已被覆盖，它们的 \( y \) 不变。约束为 \( y_ {23}+y_ {34}+y_ {14} \le 1 \)，当前 \( y_ {23}=1/3, y_ {14}=1/3, y_ {34}=0 \)，所以和为 \( 2/3 \)。增加 \( y_ {34} \)，当 \( y_ {34}=1/3 \) 时，约束变为 \( 1/3+1/3+1/3=1 \)，变紧，选择 (3,4) 加入 \( D \)。现在 \( D=\{(1,2), (3,4)\} \)。但 (1,2) 和 (3,4) 不相邻，所以边 (2,3) 和 (1,4) 被覆盖了吗？边 (2,3) 与 (1,2) 相邻，所以被覆盖；边 (1,4) 与 (1,2) 相邻，也被覆盖。但边 (1,2) 和 (3,4) 自身被覆盖。所以所有边都被覆盖。解的大小为2，是最优的。所以算法仍然找到了最优解。这提示：也许最小边控制集的整数规划松弛是精确的？不，因为问题是NP难的，所以整数规划松弛应该有间隙。实际上，考虑一个5个顶点的图：一个三角形 (1,2,3) 加上一个悬挂边 (3,4) 和 (4,5)。边集合：\( e_ 1=(1,2), e_ 2=(2,3), e_ 3=(1,3), e_ 4=(3,4), e_ 5=(4,5) \)。整数最优解：可以选择 \( e_ 2 \) 和 \( e_ 4 \)，覆盖所有边。大小2。线性规划松弛：最优解可能赋值 \( x_ {e_ 1}=x_ {e_ 2}=x_ {e_ 3}=0.5, x_ {e_ 4}=1, x_ {e_ 5}=0.5? \) 检查约束：对 \( e_ 1 \)，相邻边为 \( e_ 1,e_ 2,e_ 3 \)，和=0.5+0.5+0.5=1.5>1，满足。对 \( e_ 5 \)，相邻边为 \( e_ 4,e_ 5 \)，和=1+0.5=1.5>1。目标值=0.5+0.5+0.5+1+0.5=3。但整数最优为2，所以有间隙。我们的算法在这个实例上：初始所有 \( y=0 \)。增加所有边的 \( y \)。当增加到某个值，假设同时增加，直到某约束变紧。边 \( e_ 4 \) 的相邻边只有 \( e_ 3,e_ 4,e_ 5 \)? 实际 \( e_ 4=(3,4) \)，相邻边有：\( e_ 2=(2,3) \), \( e_ 3=(1,3) \), \( e_ 4 \), \( e_ 5=(4,5) \)。所以约束为 \( y_ 2+y_ 3+y_ 4+y_ 5 \le 1 \)。边 \( e_ 5 \) 相邻边有 \( e_ 4,e_ 5 \)。当所有 \( y \) 增加到 \( 1/4 \) 时，边 \( e_ 4 \) 的约束变为 \( 4* (1/4)=1 \)，变紧。算法选择 \( e_ 4 \) 加入 \( D \)，覆盖 \( e_ 2,e_ 3,e_ 4,e_ 5 \)。剩下 \( e_ 1 \) 未被覆盖（因为 \( e_ 1 \) 与 \( e_ 4 \) 不相邻）。然后增加 \( y_ 1 \)，同时 \( e_ 1 \) 的相邻边有 \( e_ 1,e_ 2,e_ 3 \)，其中 \( y_ 2=y_ 3=1/4 \)，所以当 \( y_ 1 \) 增加到 \( 1/2 \) 时，约束 \( y_ 1+y_ 2+y_ 3=1/2+1/4+1/4=1 \) 变紧，选择 \( e_ 1 \) 加入 \( D \)。最终 \( D=\{e_ 4,e_ 1\} \)，大小2，是最优的。所以算法还是找到了最优。这说明该算法可能总是精确求解？实际上，最小边控制集问题虽然NP难，但其线性规划松弛可能是整数解？不，因为整数规划是覆盖类型，通常有间隙。但经典结论：最小边控制集的原始-对偶算法是2-近似的。我们的分析哪里出错了？我们需要重新审视近似比证明。标准分析：设算法选中的边集为 \( D \)。对每条边 \( e \in E \)，定义其“见证”边 \( f(e) \) 为算法中覆盖 \( e \) 的边（即当 \( e \) 被覆盖时，加入 \( D \) 的那条边）。注意 \( f(e) \) 与 \( e \) 相邻或相同。则对每条选中的边 \( f \in D \)，考虑集合 \( S_ f = \{ e \in E \mid f(e) = f \} \)。显然 \( \{S_ f\} {f \in D} \) 是 \( E \) 的一个划分。由算法，当 \( f \) 被选中时，对所有 \( e \in S_ f \)，有 \( y_ e \) 相同（因为它们同步增加）？实际上，在 \( f \) 被选中时，所有 \( e \in S_ f \) 的 \( y_ e \) 都等于当前值，设为 \( \delta_ f \)。所以 \( \sum {e \in S_ f} y_ e = |S_ f| \cdot \delta_ f \)。由于 \( f \) 的约束在选中时变紧：\( \sum_ {e: f \in N(e)} y_ e = 1 \)。注意 \( S_ f \subseteq \{ e \mid f \in N(e) \} \)，所以 \( \sum_ {e \in S_ f} y_ e \le 1 \)。即 \( |S_ f| \cdot \delta_ f \le 1 \)。对偶目标值 \( \sum_ {e \in E} y_ e = \sum_ {f \in D} |S_ f| \cdot \delta_ f \le \sum_ {f \in D} 1 = |D| \)。所以 \( |D| \ge \sum_ {e} y_ e \)。由弱对偶，\( OPT \ge OPT_ {LP} \ge \sum_ {e} y_ e \)，所以 \( |D| \ge OPT \)? 这显然不对。我们实际上需要上界 \( |D| \le \alpha \sum_ {e} y_ e \)。但这里得到的是下界。正确分析应该是：由于每条边 \( e \) 最多出现在两个不同的 \( S_ f \) 中？因为一条边有两个端点，每个端点最多贡献一个选中边作为见证？考虑边 \( e = (u,v) \)。它被一条选中边 \( f(e) \) 覆盖。如果 \( f(e) \) 与 \( e \) 共享一个端点，那么另一个端点可能被另一条选中边覆盖，但 \( e \) 本身只被 \( f(e) \) 覆盖。所以每条边只出现在一个 \( S_ f \) 中。所以 \( \sum_ {f} |S_ f| = |E| \)。但 \( |D| = \sum_ f 1 \)。我们需要关联 \( |D| \) 和 \( \sum_ f |S_ f| \cdot \delta_ f \)。由于 \( \delta_ f \le 1/|S_ f| \)（因为 \( |S_ f| \cdot \delta_ f \le 1 \)），所以 \( \sum_ e y_ e = \sum_ f |S_ f| \cdot \delta_ f \le \sum_ f 1 = |D| \)。这仍然是下界。实际上，经典原始-对偶分析通常证明 \( |D| \le 2 \sum_ e y_ e \)。为了得到这个，我们需要每个 \( |S_ f| \ge 2 \)？不一定，可能为1。但注意，当 \( |S_ f| = 1 \) 时，\( \delta_ f \le 1 \)，但 \( |S_ f| \cdot \delta_ f = \delta_ f \le 1 = 1 \cdot 1 \)，所以 \( |D| = \sum_ f 1 \ge \sum_ f |S_ f| \cdot \delta_ f = \sum_ e y_ e \)。所以 \( |D| \) 可能大于对偶和。但我们需要上界。我们换一个思路。考虑整数规划约束的系数矩阵。约束 \( \sum_ {f \in N(e)} x_ f \ge 1 \) 中，每个变量 \( x_ f \) 出现在所有满足 \( f \in N(e) \) 的约束中，即出现在边 \( f \) 自身和所有与 \( f \) 相邻的边的约束中。所以每个变量出现在最多 \( 2\Delta-1 \) 个约束中？实际上，一条边有两个端点，每个端点度数最多为 \( \Delta \)，所以相邻边最多为 \( 2(\Delta-1) \) 条，加上自身，最多 \( 2\Delta-1 \) 条。但这与近似比无关。原始-对偶算法的标准分析：设对偶解为 \( y \)，原始解为 \( x \)（整数）。由互补松弛条件：如果 \( x_ f > 0 \)，则对应对偶约束紧： \( \sum_ {e: f \in N(e)} y_ e = 1 \)。如果 \( y_ e > 0 \)，则对应原始约束紧： \( \sum_ {f \in N(e)} x_ f = 1 \)？不，原始约束是大于等于，所以当 \( y_ e > 0 \) 时，只能推出 \( \sum_ {f \in N(e)} x_ f = 1 \) 如果原始解是最优的。但我们的算法并不保证 \( y_ e > 0 \) 时原始约束紧。然而，在算法中，当 \( y_ e > 0 \) 时，边 \( e \) 被覆盖，所以 \( \sum_ {f \in N(e)} x_ f \ge 1 \)，但可能大于1。所以只有一半的互补松弛条件满足。近似比证明通常利用：对每个选中的 \( f \)，有 \( \sum_ {e: f \in N(e)} y_ e = 1 \)。求和得 \( \sum_ {f \in D} \sum_ {e: f \in N(e)} y_ e = |D| \)。交换求和次序：\( \sum_ {e \in E} y_ e \cdot |\{ f \in D \mid f \in N(e) \}| = |D| \)。由于每条边 \( e \) 可能被多条选中的边覆盖，即 \( |\{ f \in D \mid f \in N(e) \}| \) 可能大于1。但注意，在算法中，一旦一条边被覆盖，它的对偶变量就不再增加，但后续可能还有其他选中边与其相邻。所以 \( |\{ f \in D \mid f \in N(e) \}| \) 可以大于1。最坏情况下，一条边可能与所有选中的边相邻。但我们希望找到一个上界。考虑一条边 \( e = (u,v) \)。哪些选中边会与 \( e \) 相邻？选中边必须与 \( e \) 共享至少一个顶点。所以只有那些覆盖 \( u \) 或 \( v \) 的边可能与 \( e \) 相邻。但算法中，一个顶点可能被多条选中边关联。然而，我们可以证明：对于每个顶点，最多有两条选中边与其关联？不对。例如星形图，中心顶点关联所有选中边（如果选中多条）。但星形图中算法只选一条边。考虑一个三角形加一条悬挂边：图：三角形 (1,2), (2,3), (1,3)，加上边 (3,4)。算法可能先选 (1,2)，覆盖三角形所有边，然后 (3,4) 未被覆盖，再选 (3,4)。选中边为 (1,2) 和 (3,4)。顶点3关联两条选中边：(1,2) 不与3相邻？(1,2) 与顶点3不相邻。所以顶点3只关联 (3,4)。顶点1关联 (1,2)。所以每个顶点最多关联一条选中边？不一定。考虑一个图：两个三角形共享一条边。顶点集合1,2,3,4，边： (1,2), (2,3), (1,3) 形成一个三角形，另一个三角形 (2,3), (3,4), (2,4)。共享边 (2,3)。算法可能先选 (2,3)，覆盖所有边？(2,3) 覆盖自身，(1,2), (1,3), (2,4), (3,4) 都与 (2,3) 相邻，所以全部覆盖。所以只选一条边。所以算法往往选出很少的边。实际上，可以证明：算法选出的边构成一个极大匹配？因为每条选中的边会覆盖所有与其相邻的边，所以选中边之间没有公共顶点？如果有公共顶点，那么一条边会覆盖另一条边，但另一条边不会在之后被选中，因为已被覆盖。所以选中边集合是一个匹配。因为如果两条选中边共享一个顶点，那么先选中的那条会覆盖后选中的那条，所以后选中的那条不会被选中。因此，算法选中的边集 \( D \) 是一个匹配。于是，每条边 \( e \) 最多与两条 \( D \) 中的边相邻（每个端点最多关联一条 \( D \) 中的边，因为 \( D \) 是匹配）。所以 \( |\{ f \in D \mid f \in N(e) \}| \le 2 \)。于是： \[ |D| = \sum_ {e \in E} y_ e \cdot |\{ f \in D \mid f \in N(e) \}| \le 2 \sum_ {e \in E} y_ e \le 2 \cdot OPT_ {LP} \le 2 \cdot OPT \] 因此算法是2-近似的。第六步：算法步骤详述输入无向图 \( G=(V,E) \)。初始化：\( x_ e = 0 \) 对所有 \( e \in E \)；\( y_ e = 0 \) 对所有 \( e \in E \)；\( D = \emptyset \)；所有边标记为未覆盖。当存在未覆盖的边时：设 \( U \) 为未覆盖边的集合。同时增加所有 \( e \in U \) 的 \( y_ e \)，直到存在某条边 \( f \in E \) 使得对偶约束 \( \sum_ {e: f \in N(e)} y_ e = 1 \) 成立（注意：即使 \( f \) 已覆盖也可能触发？约束对所有边 \( f \) 都检查。但已覆盖的边的 \( y_ e \) 不增加，所以其约束不会变紧，除非之前已紧）。将 \( f \) 加入 \( D \)，设 \( x_ f = 1 \)。将所有满足 \( f \in N(e) \) 的边 \( e \) 标记为已覆盖（即所有与 \( f \) 相邻的边，包括 \( f \) 自身）。输出 \( D \)。实现时，不需要真的逐步增加 \( y_ e \)，可以通过计算最小增量来模拟。第七步：举例说明考虑一个简单图：路径图 \( P_ 4 \)：边依次为 \( e_ 1=(1,2), e_ 2=(2,3), e_ 3=(3,4) \)。初始所有边未覆盖，\( y_ 1=y_ 2=y_ 3=0 \)。同时增加 \( y_ 1, y_ 2, y_ 3 \)。约束：对 \( e_ 1 \): 相邻边 \( e_ 1, e_ 2 \)，约束 \( y_ 1+y_ 2 \le 1 \)。对 \( e_ 2 \): 相邻边 \( e_ 1, e_ 2, e_ 3 \)，约束 \( y_ 1+y_ 2+y_ 3 \le 1 \)。对 \( e_ 3 \): 相邻边 \( e_ 2, e_ 3 \)，约束 \( y_ 2+y_ 3 \le 1 \)。当增加到 \( y_ 1=y_ 2=y_ 3=1/3 \) 时，约束 \( e_ 2 \) 变为紧。选择 \( e_ 2 \) 加入 \( D \)，覆盖 \( e_ 1, e_ 2, e_ 3 \)。所有边被覆盖，算法结束。\( D=\{e_ 2\} \)，大小1。实际上最小边控制集至少为1，因为一条边可以控制所有边（因为相邻）。所以是最优解。第八步：总结本问题通过整数规划建模，利用原始-对偶方法设计了一个近似算法。算法每次选择对偶约束变紧的边加入解，直到所有边被覆盖。由于选中边构成一个匹配，每条边最多与两条选中边相邻，因此近似比为2。该算法简单高效，适用于大规模图的最小边控制集近似求解。