基于线性规划的图最大匹配问题的多项式时间原始-对偶近似算法求解示例
题目描述
我们考虑一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。一个匹配是边集的一个子集，使得任意两条边不共享公共顶点。最大匹配问题是寻找一个包含边数最多的匹配。虽然最大匹配存在多项式时间精确算法（如Edmonds'开花算法），但我们可以从线性规划的角度，设计一个基于原始-对偶框架的多项式时间近似算法。这个算法虽然对最大匹配是精确的，但其原始-对偶设计思想是学习组合优化中近似算法的经典范例。本示例将展示如何将最大匹配建模为整数规划，松弛为线性规划，然后通过原始-对偶方法构造整数解，并证明其最优性。
解题步骤
- 整数规划建模
对每条边 \(e \in E\) 引入0-1变量 \(x_e\)：若 \(e\) 在匹配中则 \(x_e = 1\)，否则为0。对于每个顶点 \(v \in V\)，匹配要求最多有一条关联边被选中，即顶点的度约束。最大匹配的整数规划模型为：
\[ \begin{aligned} \max \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \\ & x_e \in \{0,1\}, \quad \forall e \in E \end{aligned} \]
其中 \(\delta(v)\) 表示与顶点 \(v\) 关联的边集。
- 线性规划松弛
将整数约束松弛为线性约束：
\[ \begin{aligned} \max \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \\ & x_e \geq 0, \quad \forall e \in E \end{aligned} \]
注意：约束 \(x_e \leq 1\) 是冗余的，因为每个顶点度约束已隐含 \(x_e \leq 1\)。
- 写出对偶线性规划
为每个顶点约束引入对偶变量 \(y_v \geq 0\)。对偶线性规划为：
\[ \begin{aligned} \min \quad & \sum_{v \in V} y_v \\ \text{s.t.} \quad & y_u + y_v \geq 1, \quad \forall e = (u,v) \in E \\ & y_v \geq 0, \quad \forall v \in V \end{aligned} \]
对偶问题的可行解可解释为给每个顶点赋一个非负权值 \(y_v\)，使得每条边两端点权值之和至少为1。
-
设计原始-对偶近似算法
算法思路：从对偶可行解出发，通过互补松弛条件指导构造原始整数解（匹配）。- 初始化：设所有 \(y_v = 0\)，所有边未被标记。
- 迭代过程：
- 检查是否存在边 \(e = (u,v)\) 满足 \(y_u + y_v < 1\) 且未被标记。若没有，转到步骤3。
- 同时增加 \(y_u\) 和 \(y_v\)（以相同速率），直到 \(y_u + y_v = 1\)。将边 \(e\) 标记为“紧”。
- 当所有边都满足 \(y_u + y_v \geq 1\) 时，停止增加对偶变量。此时得到对偶可行解 \(y\)。
- 构造匹配：考虑所有紧边（即满足 \(y_u + y_v = 1\) 的边）。在这些边构成的子图中，贪心地选取一个极大匹配 \(M\)（例如，遍历边，若边两端点都未匹配，则加入匹配）。
- 输出匹配 \(M\)。
-
算法分析
- 可行性：构造的 \(M\) 是匹配，因为贪心选择保证无两条边共享顶点。
- 最优性证明：
设算法得到的匹配为 \(M\)，对偶解为 \(y\)。由构造，每条匹配边 \(e=(u,v) \in M\) 满足 \(y_u + y_v = 1\)。对每个顶点 \(v\)，定义其贡献：若 \(v\) 被匹配，记其匹配边为 \(e\)，则 \(y_v\) 是 \(e\) 上对偶和的一半（因为两端点各贡献一半）；若 \(v\) 未被匹配，则 \(y_v = 0\)。因此，
\[ \sum_{v \in V} y_v = \sum_{e \in M} (y_u + y_v) = |M|. \]
由对偶线性规划，任何对偶可行解的目标值 $ \sum_{v} y_v $ 是原始线性规划最优值的上界，从而也是整数规划最优值（记最大匹配大小为 $ \text{OPT} $）的上界。故
\[ |M| = \sum_{v} y_v \geq \text{OPT}? \]
实际上，由于 $ y $ 是对偶可行解，有 $ \sum_{v} y_v \geq \text{OPT}_{\text{LP}} \geq \text{OPT} $。但我们有 $ |M| = \sum_{v} y_v $，因此 $ |M| \geq \text{OPT} $？这显然不可能，因为匹配不可能超过最大匹配。这里需要小心：我们构造的 $ y $ 不是任意的对偶可行解，它满足额外性质，使得 $ \sum_{v} y_v = |M| $，而且 $ \sum_{v} y_v \leq \text{OPT}_{\text{LP}} $？实际上，算法通过互补松弛条件保证了强对偶成立。更严格的分析：
- 由对偶可行性，$ \sum_{v} y_v \geq \text{OPT}_{\text{LP}} $。
- 由算法构造，匹配 $ M $ 的大小等于 $ \sum_{v} y_v $。
- 但线性规划最优值 $ \text{OPT}_{\text{LP}} $ 可能大于整数最优值 $ \text{OPT} $。然而对于匹配问题的线性规划松弛，其最优解总是整数（因为约束矩阵是全幺模矩阵），所以 $ \text{OPT}_{\text{LP}} = \text{OPT} $。
因此，$ |M| = \sum_{v} y_v = \text{OPT}_{\text{LP}} = \text{OPT} $，即算法得到的是最大匹配。
- 时间复杂度：每次迭代至少标记一条新边，至多 \(|E|\) 次迭代，每次更新对偶变量可在常数时间内完成，构造匹配需 \(O(|E|)\)，总时间复杂度为 \(O(|E|)\)，是多项式的。
- 举例说明
考虑一个简单图：三角形 \(K_3\)（三个顶点 \(a,b,c\)，边 \(ab, bc, ca\)）。- 初始化：\(y_a=y_b=y_c=0\)。
- 迭代1：选边 \(ab\)，增加 \(y_a, y_b\) 至0.5，标记 \(ab\) 为紧。
- 迭代2：剩下边 \(bc, ca\) 都不满足 \(y_u+y_v<1\)？检查：对 \(bc\)，\(y_b+y_c=0.5+0=0.5<1\)，增加 \(y_b, y_c\) 至0.5+δ，当 δ=0.5 时，\(y_b=1.0, y_c=0.5\)，标记 \(bc\) 为紧。
- 迭代3：对 \(ca\)，\(y_c+y_a=0.5+0.5=1.0\)，已满足。算法停止。
- 对偶解：\((y_a,y_b,y_c)=(0.5,1.0,0.5)\)，和=2.0。
- 紧边：\(ab, bc\)。在紧边子图中贪心匹配：先取 \(ab\)，则 \(bc\) 不可用（因为顶点b已匹配），得到匹配 \(M=\{ab\}\)，大小1。但三角形最大匹配为1，算法最优。
注意：若贪心顺序不同可能得匹配 \(\{bc\}\)，大小仍为1。
结论
本示例展示了如何利用原始-对偶方法为最大匹配问题设计多项式时间算法。该算法通过构造对偶可行解，利用互补松弛条件构造原始整数解，并证明了所得匹配是最优的。虽然最大匹配有多项式时间精确算法，但这种方法展示了原始-对偶框架在组合优化问题中的应用模式。