基于线性规划的图最小边支配集问题的线性规划模型构建、松弛与舍入算法求解示例
第一部分：问题描述
边支配集是图论中的一个重要概念。给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。一个边支配集定义为一个边子集 \(D \subseteq E\)，使得图中每一条边（无论它是否在 \(D\) 中）都与 \(D\) 中的至少一条边相邻。这里，两条边相邻是指它们共享一个公共顶点。
最小边支配集问题 就是在图 \(G\) 中找到一个基数（即边数）最小的边支配集。这是一个经典的NP难组合优化问题。在本示例中，我们将：
- 为其构建一个整数线性规划模型。
- 将其整数约束松弛为线性规划，并求解这个线性规划松弛。
- 设计一个简单的舍入算法，将松弛解转化为一个可行的整数解（即一个有效的边支配集），并分析其近似比。
第二部分：模型构建
设图 \(G = (V, E)\)，共有 \(m = |E|\) 条边。我们为每条边 \(e \in E\) 引入一个二进制决策变量 \(x_e\)：
\[x_e = \begin{cases} 1, & \text{如果边 } e \text{ 被选入边支配集 } D \\ 0, & \text{否则} \end{cases} \]
目标：最小化所选边的总数，即 \(\min \sum_{e \in E} x_e\)。
约束：对于任意一条边 \(f = (u, v) \in E\)，它必须被支配。哪些边能支配 \(f\)？
- 首先是 \(f\) 自身（如果被选中）。
- 其次，所有与 \(f\) 相邻的边也能支配 \(f\)。与 \(f\) 相邻的边是指所有与顶点 \(u\) 或顶点 \(v\) 相关联的边（不包括 \(f\) 自身）。
- 为了形式化，对于一条给定的边 \(f\)，定义其“封闭邻域” \(N[f] = \{ e \in E \ | \ e \text{ 与 } f \text{ 相邻，或者 } e = f \}\)。
那么，对于每一条边 \(f \in E\)，支配它的约束可以写为：
\[\sum_{e \in N[f]} x_e \ge 1 \]
这个不等式确保了至少有一条边在 \(f\) 的封闭邻域中被选中，从而 \(f\) 被支配。
整数线性规划模型 为：
\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in N[f]} x_e \ge 1, \quad \forall f \in E \\ & x_e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \]
这是一个精确的整数规划模型，其最优解对应最小边支配集。
第三部分：线性规划松弛
由于整数规划是NP难的，我们将其松弛为线性规划，以获取计算上可处理的下界，并作为舍入的基础。
线性规划松弛 只需将整数约束 \(x_e \in \{0, 1\}\) 替换为非负约束：
\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in N[f]} x_e \ge 1, \quad \forall f \in E \\ & x_e \ge 0, \quad \forall e \in E \end{aligned} \]
注意，我们实际上不必显式写出 \(x_e \le 1\)，因为约束 \(\sum_{e \in N[f]} x_e \ge 1\) 和最小化目标会自然倾向于将解值限制在合理范围。不过，最优解中 \(x_e^*\) 可能会大于1，但考虑到最小化目标和所有约束都是“\(\ge 1\)”，在最优解中，\(x_e^*\) 通常会落在 \([0, 1]\) 区间，但理论上也可能大于1。我们将其求解为一个标准的线性规划。
求解线性规划松弛：
我们可以使用单纯形法、内点法等任何线性规划求解器来获得松弛问题的最优解 \(x^* = (x_e^*)_{e \in E}\)。设其最优目标值为 \(OPT_{LP}\)。显然，由于松弛扩大了可行域，有 \(OPT_{LP} \le OPT\)，其中 \(OPT\) 是原整数规划（最小边支配集）的最优值。
第四部分：舍入算法设计
我们现在需要将分数解 \(x^*\) 舍入为一个整数解 \(\hat{x}\)，使其满足所有约束，并希望 \(\sum \hat{x}_e\) 不要比 \(OPT_{LP}\) 大太多。
一个直接而有效的策略是简单阈值舍入。其核心思想是：每条边 \(e\) 的分数值 \(x_e^*\) 可以看作是“被选中的概率”或“被覆盖的强度”。我们设定一个阈值，将分数值足够大的边直接选入支配集。
算法步骤：
- 求解线性规划松弛：得到最优分数解 \(x^*\)。
- 初始化：设整数解集合 \(D = \emptyset\)（空集）。
- 阈值舍入：对于每一条边 \(e \in E\)：
- 如果 \(x_e^* \ge \frac{1}{2}\)，则将边 \(e\) 加入 \(D\)（即令 \(\hat{x}_e = 1\)）。
- 否则，不加入（即令 \(\hat{x}_e = 0\)）。
- 输出：边集 \(D\) 作为我们找到的边支配集。
第五部分：可行性证明
我们需要证明算法输出的集合 \(D\) 确实是一个边支配集。
证明：
- 考虑任意一条边 \(f \in E\)。根据线性规划的约束，我们有 \(\sum_{e \in N[f]} x_e^* \ge 1\)。
- 边 \(f\) 的封闭邻域 \(N[f]\) 包含 \(f\) 自身以及与 \(f\) 相邻的边。这个不等式说明，在 \(f\) 的封闭邻域中，所有边的 \(x^*\) 值之和至少为1。
- 现在，在舍入步骤中，对于 \(N[f]\) 中的边，如果它的 \(x_e^* < 1/2\)，我们将其舍入为0；如果 \(x_e^* \ge 1/2\)，我们将其舍入为1。
- 关键观察：为了使舍入后 \(f\) 被支配，我们需要在 \(N[f]\) 中至少有一条边被舍入为1。我们用反证法证明这一点。
- 假设舍入后，\(N[f]\) 中没有任何边的 \(\hat{x}_e = 1\)。这意味着对于所有 \(e \in N[f]\)，都有 \(x_e^* < 1/2\)。
- 那么，\(\sum_{e \in N[f]} x_e^* < \sum_{e \in N[f]} \frac{1}{2} = \frac{|N[f]|}{2}\)。
- 但是，\(|N[f]|\) 是多少？一条边 \(f\) 最多能与多少条边相邻？在简单无向图中，一条边关联两个顶点。设顶点 \(u\) 的度数为 \(d_u\)，顶点 \(v\) 的度数为 \(d_v\)。那么，与 \(f\) 相邻的边数是 \((d_u - 1) + (d_v - 1) = d_u + d_v - 2\)。再加上 \(f\) 自身，有 \(|N[f]| = d_u + d_v - 1\)。这个值可以很大，但我们无法直接得到一个小于1的上界。
- 为了严格证明，我们需要一个更巧妙的论证。注意，我们舍入的条件是 \(x_e^* \ge 1/2\)。如果 \(N[f]\) 中所有边的 \(x_e^*\) 都严格小于 \(1/2\)，那么它们的和最大是多少？假设有 \(k\) 条边，每条边值小于 \(1/2\)，那么和小于 \(k/2\)。但这并不能直接与约束 \(\ge 1\) 矛盾，除非 \(k \le 2\)。
- 实际上，这个简单的“1/2阈值”舍入不能保证可行性！这是一个常见的陷阱。考虑一个三角形图（3个顶点，3条边）。线性规划松弛的一个最优解可能是 \(x_{ab}^* = x_{bc}^* = x_{ca}^* = 0.5\)，它满足每条边的邻域和为1（例如，对于边ab，其邻域包括ab(0.5), bc(0.5), ca(0.5)，和为1.5）。但如果我们用1/2阈值舍入，所有边都满足 \(x_e^* = 0.5 \ge 0.5\)，所以全被选中，结果是可行的，但这只是巧合。
- 反例：考虑一个由两条边共享一个公共顶点构成的“V”形图（三个顶点a, b, c，边 \(e_1=(a,b), e_2=(b,c)\)）。线性规划松弛的一个可能最优解是 \(x_{e1}^* = x_{e2}^* = 0.5\)。约束：对于 \(e1\)，其邻域 \(N[e1] = \{e1, e2\}\)，和为1；对于 \(e2\) 同理。用1/2阈值舍入，两条边都被选中，是可行的支配集（大小为2）。但最优解其实是选中其中一条边即可（大小为1）。算法给出了可行解，但近似比是2。然而，我们需要证明对于所有实例，舍入后都可行。
- 为了修正可行性，我们需要更强的论证或不同的舍入策略。实际上，对于边支配集，已知的一种简单有效舍入是直接选择所有分数值为正的边，但这样近似比很差。另一种常用方法是利用线性规划的对偶和原始-对偶方法。但为了本示例的教学连贯性，我们采用一个经典且可证明的舍入策略：将阈值设为 \(1/\Delta\)，其中 \(\Delta\) 是图的最大度数。但更常见的、能保证可行性和常数近似比的方法是：
修正的舍入算法（简单贪婪舍入）：
求解LP松弛得到 \(x^*\)。然后，我们不仅看单条边的值，而是考虑“覆盖”关系。一个等价但更鲁棒的方法是：
- 求解LP松弛。
- 初始化 \(D = \emptyset\)。
- 当图中还存在未被支配的边时：
a. 选择一条分数值 \(x_e^*\) 最大的边 \(e\)（或者随机地，以概率与 \(x_e^*\) 成比例地选择一条边）。
b. 将 \(e\) 加入 \(D\)。
c. 从图中移除所有已被 \(e\) 支配的边（即所有与 \(e\) 相邻的边，以及 \(e\) 自身）。 - 输出 \(D\)。
这个算法本质上是一个基于LP指导的贪婪算法。由于每次选择一条边会移除其封闭邻域内的所有边，这保证了算法终止时，所有边都被支配。其近似比分析通常基于线性规划解的总和。
为了简化并与最初的线性规划模型直接挂钩，我们采用一个理论上有保证的舍入方案：将阈值设为 \(1/2\)，但需要证明可行性。实际上，对于边支配集，简单的 \(1/2\) 阈值舍入并不总是可行。一个已知的可行舍入是：选择所有满足 \(x_e^* \ge 1/d_{max}\) 的边，其中 \(d_{max}\) 是图的最大度数，但这会降低近似比。
为了本示例的完整性，我们采用一个在理论上可证明的舍入方法，它基于对约束的观察。注意，对于每条边 \(f\)，其封闭邻域 \(N[f]\) 包含 \(f\) 和所有与 \(f\) 相邻的边。如果我们能证明，在 \(x^*\) 中，对于每条边 \(f\)，其封闭邻域 \(N[f]\) 中至少有一条边的值不小于某个固定的正数 \(\alpha\)，那么设置阈值为 \(\alpha\) 就能保证可行性。但 \(\alpha\) 可能与图的结构有关。
实际上，一个标准且简单的常数近似算法是：先求解LP松弛得到 \(x^*\)，然后构造一个新的边集 \(D'\)，包含所有满足 \(x_e^* > 0\) 的边。然后，从 \(D'\) 中移去所有“冗余”的边（即如果移除某条边，剩下的集合仍然是边支配集，则移除它）。 这个过程是多项式时间的，并且可以证明，最终得到的边支配集 \(D\) 的大小不超过 \(2 * OPT_{LP}\)，因此是一个2-近似解。因为 \(OPT_{LP} \le OPT\)，所以 \(|\hat{D}| \le 2 * OPT\)。
我们采用这个“移去冗余边”的后处理步骤来保证可行性并得到近似比。
修正后的算法步骤：
- 求解线性规划松弛，得到最优解 \(x^*\)。
- 令初始候选集 \(D' = \{ e \in E \ | \ x_e^* > 0 \}\)。（所有分数值大于0的边）
- 贪心移除冗余边：按任意顺序检查 \(D'\) 中的每条边 \(e\)。如果将 \(e\) 从 \(D'\) 中移除后，\(D' \setminus \{e\}\) 仍然是一个边支配集（即对于每条边 \(f \in E\)，其封闭邻域与 \(D'\setminus\{e\}\) 的交集非空），那么就将 \(e\) 永久移除。
- 最终剩下的集合 \(D\) 即为输出的边支配集。
第六部分：近似比分析
我们证明上述算法是一个2-近似算法。
设 \(D\) 是算法输出的边支配集。我们需要证明 \(|D| \le 2 \cdot OPT_{LP} \le 2 \cdot OPT\)。
证明思路：
- 上界：由于 \(D \subseteq D'\)，且 \(D'\) 只包含分数值大于0的边，我们有 \(|D| \le |D'|\)。但 \(|D'|\) 可能很大，我们需要将其与 \(OPT_{LP}\) 联系起来。
- 关键引理：在算法第3步贪心移除冗余边之后，最终的边支配集 \(D\) 具有一个性质：\(D\) 中的边是互相“远离”的，具体来说，没有两条不同的边 \(e, f \in D\) 是相邻的。为什么？因为如果 \(e\) 和 \(f\) 相邻，那么考虑其中一条边，比如 \(e\)。由于 \(e\) 和 \(f\) 相邻，\(f\) 能支配所有与 \(e\) 相邻的边（包括 \(e\) 自身）。那么当我们检查 \(e\) 是否可以移除时，即使移除 \(e\)，\(f\) 的存在依然能保证所有原本被 \(e\) 支配的边（即 \(N[e]\) 中的边）仍然被支配（因为 \(f \in N[e]\)）。所以 \(e\) 会是冗余的，在步骤3中应该已经被移除了。这与 \(e \in D\) 矛盾。因此，\(D\) 中的边构成一个匹配（一组没有公共顶点的边）。
- 利用线性规划约束：因为 \(D\) 是一个匹配，所以 \(D\) 中的边对应的约束是“松散耦合”的。更精确地说，对于 \(D\) 中的每条边 \(e\)，考虑线性规划中对应 \(e\) 自身的约束：
\[ \sum_{g \in N[e]} x_g^* \ge 1. \]
由于 $D$ 是匹配，$D$ 中不同的边对应的封闭邻域 $N[e]$ 是互不相交的（因为如果两条边没有公共顶点，它们的封闭邻域可能共享顶点吗？不会，因为如果两条边 $e$ 和 $f$ 不相邻，它们没有公共顶点，那么与 $e$ 关联的顶点和与 $f$ 关联的顶点是不同的。因此，与 $e$ 关联的边集和与 $f$ 关联的边集没有交集，即 $N[e] \cap N[f] = \emptyset$）。这是一个重要性质。
- 求和：我们对所有 \(e \in D\) 对应的约束求和：
\[ \sum_{e \in D} \left( \sum_{g \in N[e]} x_g^* \right) \ge \sum_{e \in D} 1 = |D|. \]
由于 $D$ 是匹配，左边和式中的项 $x_g^*$ 来自互不相交的边集 $\{N[e] : e \in D\}$。因此，左边的和等于 $\sum_{g \in \bigcup_{e \in D} N[e]} x_g^*$。这个和显然小于等于所有边的 $x^*$ 值之和，即 $OPT_{LP}$。所以：
\[ OPT_{LP} = \sum_{g \in E} x_g^* \ge \sum_{g \in \bigcup_{e \in D} N[e]} x_g^* \ge |D|. \]
等等，这得到了 $|D| \le OPT_{LP}$，这似乎是一个最优解？这里有一个微妙之处：集合 $\bigcup_{e \in D} N[e]$ 并不一定包含所有边，因为 $D$ 是匹配，它的邻域并集可能只是 $E$ 的一个子集。所以不等式 $\sum_{g \in E} x_g^* \ge \sum_{g \in \bigcup_{e \in D} N[e]} x_g^*$ 成立，但我们不能直接得到 $|D| \le OPT_{LP}$，因为左边的和是 $|D|$，右边的和是 $OPT_{LP}$ 的一部分，可能小于 $OPT_{LP}$。实际上，我们需要一个更紧的界。
- 修正求和：注意，对于每条边 \(e \in D\)，其约束是 \(\sum_{g \in N[e]} x_g^* \ge 1\)。由于 \(N[e]\) 是互不相交的，我们将这 \(|D|\) 个不等式相加，得到：
\[ \sum_{e \in D} \sum_{g \in N[e]} x_g^* \ge |D|. \]
交换求和顺序，左边是 $\sum_{g \in E} (x_g^* \cdot |\{e \in D : g \in N[e]\}|)$。现在，对于任意一条边 $g \in E$，它可能出现在多少个不同的 $N[e]$ 中（其中 $e \in D$）？因为 $D$ 是匹配，所以 $g$ 最多与 $D$ 中的两条边相邻（如果 $g$ 的一个端点与 $D$ 中的一条边关联，另一个端点与 $D$ 中的另一条边关联，这是可能的吗？不可能，因为 $D$ 是匹配，它的边没有公共顶点。所以一条边 $g$ 最多与 $D$ 中的一条边相邻，因为如果它和两条 $D$ 中的边相邻，那两条 $D$ 中的边就会共享 $g$ 的一个端点，从而彼此相邻，与匹配矛盾）。因此，对于任何 $g$，有 $|\{e \in D : g \in N[e]\}| \le 2$。所以，
\[ \sum_{e \in D} \sum_{g \in N[e]} x_g^* = \sum_{g \in E} x_g^* \cdot |\{e \in D : g \in N[e]\}| \le 2 \sum_{g \in E} x_g^* = 2 \cdot OPT_{LP}. \]
结合不等式，我们得到：
\[ |D| \le \sum_{e \in D} \sum_{g \in N[e]} x_g^* \le 2 \cdot OPT_{LP}. \]
因此，$|D| \le 2 \cdot OPT_{LP} \le 2 \cdot OPT$。
结论：我们设计的算法（求解LP松弛，取所有正分数边，然后贪心移除冗余边）能够输出一个可行的边支配集 \(D\)，并且其大小不超过最优解的2倍。因此，这是一个2-近似算法。
第七部分：小结与扩展
本示例展示了如何利用线性规划松弛和舍入技术为NP难的组合优化问题（最小边支配集）设计近似算法。关键步骤包括：
- 整数规划建模：用二进制变量和邻域约束精确描述问题。
- 线性规划松弛：放松整数约束，得到一个多项式时间可解的下界问题。
- 舍入与后处理：将分数解通过“选择正分数边 + 移除冗余边”转化为整数解。这保证了可行性，并且通过分析（利用匹配性质和约束求和）证明了2倍的近似比。
这种线性规划舍入框架是近似算法设计中的强大工具，可用于解决许多其他网络设计和覆盖问题。