基于线性规划的图最小权顶点覆盖问题的对偶方法求解示例
我们先明确题目。图的最小权顶点覆盖（Minimum Weight Vertex Cover）问题：给定一个无向图 \(G=(V,E)\)，每个顶点 \(v\) 有一个非负权重 \(w(v)\)。要求找到一个顶点子集 \(C \subseteq V\)，使得每条边至少有一个端点属于 \(C\)，且所选顶点的权重之和最小。这是一个经典的 NP-hard 问题（在一般图上），但其整数规划模型有一个非常漂亮的对偶关系，可以利用线性规划松弛和对偶理论来设计近似算法或理解问题的结构。今天我们不设计近似算法，而是专注于如何建立其整数规划模型，写出其对偶线性规划，并通过求解对偶问题来获得原问题的最优分数解（即线性规划松弛的最优解），进而理解原问题与对偶问题之间的组合关系。
1. 问题建模
设变量 \(x_v\) 表示顶点 \(v\) 是否被选入覆盖集：
\[x_v = \begin{cases} 1, & \text{如果顶点 } v \text{ 在覆盖中} \\ 0, & \text{否则} \end{cases} \]
每条边 \(e = (u,v)\) 必须被覆盖，即 \(u\) 和 \(v\) 至少有一个在覆盖中：\(x_u + x_v \ge 1\)。
最小化总权重：
\[\min \sum_{v \in V} w_v x_v \]
约束为：
\[x_u + x_v \ge 1, \quad \forall (u,v) \in E \]
\[ 0 \le x_v \le 1, \quad \forall v \in V \]
但这是整数规划（IP），因为我们要求 \(x_v \in \{0,1\}\)。为了使用线性规划，我们松弛整数约束，允许 \(x_v\) 在 \([0,1]\) 中取任意实数值，得到线性规划（LP）：
\[\text{(P)} \quad \min \sum_{v \in V} w_v x_v \]
\[ \text{s.t.} \quad x_u + x_v \ge 1, \quad \forall (u,v) \in E \]
\[ 0 \le x_v \le 1, \quad \forall v \in V \]
注意，由于目标是最小化且权重非负，实际上上界约束 \(x_v \le 1\) 是多余的（如果某个 \(x_v > 1\)，可以降到 1 而不违反边约束且降低目标值），但保留它便于我们后面写出对称的对偶形式。
2. 写出对偶线性规划
我们为每条边 \(e = (u,v)\) 的覆盖约束 \(x_u + x_v \ge 1\) 引入对偶变量 \(y_e \ge 0\)。
为每个顶点 \(v\) 的上界约束 \(x_v \le 1\) 引入对偶变量 \(z_v \ge 0\)（注意，原问题有约束 \(x_v \ge 0\)，但它在标准对偶形式中对应符号条件，这里我们按步骤推导）。
将原问题（P）写成标准形式：
最小化 \(c^T x\)，约束为 \(Ax \ge b, x \ge 0\)。
我们需将 \(x_v \le 1\) 改写成 \(-x_v \ge -1\)。
令所有变量按顶点顺序排列为向量 \(x = (x_1, x_2, \dots, x_n)\)，目标系数 \(c_v = w_v\)。
约束分两部分：
- 边覆盖约束：对每条边 \(e=(u,v)\)，有 \(x_u + x_v \ge 1\)。在矩阵 \(A\) 中，该行在 \(u,v\) 位置为 1，其余为 0，右侧 \(b_e = 1\)。
- 上界约束：对每个顶点 \(v\)，有 \(-x_v \ge -1\)。在矩阵 \(A\) 中，该行只有第 \(v\) 列为 -1，右侧 \(b_v' = -1\)。
合起来，约束为 \(A x \ge b\)，其中 \(b\) 的前 \(|E|\) 个分量为 1，后 \(n\) 个分量为 -1。
对偶问题是最大化 \(b^T y\)，约束为 \(A^T y \le c, y \ge 0\)。
将对偶变量也分为两组：对应对偶变量 \(y_e\)（边约束）和 \(z_v\)（上界约束），且 \(y_e \ge 0, z_v \ge 0\)。
我们逐行写出 \(A^T y \le c\)：
对于每个顶点 \(v\)，在 \(A^T\) 中对应一列，由两部分贡献：
- 来自边约束：对所有与 \(v\) 关联的边 \(e\)，\(y_e\) 的系数为 1（因为边约束中 \(x_v\) 的系数是 1）。
- 来自上界约束：只有 \(z_v\) 对应的行在 \(v\) 处系数为 -1，所以 \(z_v\) 的系数是 -1。
因此，对每个 \(v\)：
\[\sum_{e \in E: v \in e} y_e - z_v \le w_v \]
此外，\(y_e \ge 0, z_v \ge 0\)。
对偶目标函数：
\[b^T y = \sum_{e \in E} 1 \cdot y_e + \sum_{v \in V} (-1) \cdot z_v = \sum_{e \in E} y_e - \sum_{v \in V} z_v \]
所以对偶问题是：
\[\text{(D)} \quad \max \sum_{e \in E} y_e - \sum_{v \in V} z_v \]
\[ \text{s.t.} \quad \sum_{e: v \in e} y_e - z_v \le w_v, \quad \forall v \in V \]
\[ y_e \ge 0, \forall e \in E; \quad z_v \ge 0, \forall v \in V \]
我们可以简化：令 \(s_v = w_v - \sum_{e: v \in e} y_e + z_v\)，由约束知 \(s_v \ge 0\)。在目标中，我们希望最大化 \(\sum y_e - \sum z_v\)，而 \(z_v\) 非负，所以尽量让 \(z_v\) 小。但约束是 \(\sum_{e: v \in e} y_e - z_v \le w_v\)，即 \(z_v \ge \sum_{e: v \in e} y_e - w_v\)。由于 \(z_v \ge 0\)，最优时我们会取
\[z_v = \max\left(0, \sum_{e: v \in e} y_e - w_v\right) \]
代入目标，得到：
\[\sum_{e \in E} y_e - \sum_{v \in V} \max\left(0, \sum_{e: v \in e} y_e - w_v\right) \]
这是关于 \(y\) 的凹函数（因为减去一个凸函数）。但更常见的写法是保留 \(z_v\)，对偶问题（D）可以解释为：每条边 \(e\) 有一个“收益” \(y_e\)，但每个顶点 \(v\) 有一个“惩罚” \(z_v\)，且惩罚 \(z_v\) 至少要弥补边收益和超出顶点权重的部分。
3. 互补松弛条件
根据线性规划对偶理论，原问题最优解 \(x^*\) 和对偶问题最优解 \((y^*, z^*)\) 满足互补松弛条件：
- 对每条边 \(e=(u,v)\)：
\[ (x_u^* + x_v^* - 1) y_e^* = 0 \]
即如果 \(y_e^* > 0\)，则 \(x_u^* + x_v^* = 1\)（该边被恰好覆盖，称为紧边）。
- 对每个顶点 \(v\)：
\[ (x_v^* - 1) z_v^* = 0 \]
即如果 \(z_v^* > 0\)，则 \(x_v^* = 1\)。
- 对每个顶点 \(v\)：
\[ \left( w_v - \sum_{e: v \in e} y_e^* + z_v^* \right) x_v^* = 0 \]
即如果 \(x_v^* > 0\)，则 \(\sum_{e: v \in e} y_e^* - z_v^* = w_v\)。
这些条件可以帮助我们从对偶解推断原问题分数解的结构。
4. 一个小例子演示
考虑一个三角形图（3个顶点，3条边），顶点权重：\(w_1=3, w_2=2, w_3=2\)。边：\((1,2), (2,3), (1,3)\)。
原问题（P）：
\[\min 3x_1 + 2x_2 + 2x_3 \]
\[ \text{s.t.} \quad x_1 + x_2 \ge 1, \quad x_2 + x_3 \ge 1, \quad x_1 + x_3 \ge 1 \]
\[ 0 \le x_v \le 1 \]
由于是极小化，最优解不会让 \(x_v > 1\)，所以上界自动满足。
我们凭观察：若取 \(x_1=0.5, x_2=0.5, x_3=0.5\)，则目标值 \(3*0.5+2*0.5+2*0.5=3.5\)，且所有边约束恰好为 1。可以验证这是最优分数解（因为三角形的最小顶点覆盖整数解需要至少两个顶点，最小权是 4，所以分数解 3.5 更小）。
现在用对偶问题验证。对偶（D）：
\[\max y_{12}+y_{23}+y_{13} - (z_1+z_2+z_3) \]
约束：
\[y_{12}+y_{13} - z_1 \le 3 \]
\[ y_{12}+y_{23} - z_2 \le 2 \]
\[ y_{13}+y_{23} - z_3 \le 2 \]
\[ y, z \ge 0 \]
猜测一个对偶可行解：由对称性，令 \(y_{12}=y_{23}=y_{13}=t\)，并令 \(z_v\) 使得约束等号成立（为利用互补松弛，因为 \(x_v>0\) 时应有等式）。设 \(z_1 = y_{12}+y_{13} - 3 = 2t-3\)，类似 \(z_2 = 2t-2\)，\(z_3 = 2t-2\)。但 \(z_v\) 必须非负，所以要求 \(2t-3 \ge 0 \Rightarrow t \ge 1.5\)，且 \(2t-2 \ge 0\) 自动满足。
对偶目标：\(3t - [ (2t-3) + (2t-2) + (2t-2) ] = 3t - (6t -7) = 7 - 3t\)。
我们希望最大化，所以 \(t\) 应尽量小，但需 \(t \ge 1.5\)。取 \(t=1.5\)，则对偶目标 \(7-4.5=2.5\)? 等等，算错：\(3t=4.5, 6t-7=9-7=2\)，所以目标 \(4.5-2=2.5\)。但原问题最优值是 3.5，对偶值应等于原问题最优值（强对偶），所以 2.5 不对。错误在于我们假设了所有约束等号成立，但可能对某些顶点 \(z_v\) 应取 0 而不是负值。
我们重新精确求解：由互补松弛，如果 \(x_v>0\)（这里 \(x_1=x_2=x_3=0.5>0\)），则对应的对偶约束应取等号：
\[y_{12}+y_{13} - z_1 = 3 \]
\[ y_{12}+y_{23} - z_2 = 2 \]
\[ y_{13}+y_{23} - z_3 = 2 \]
又由边的互补松弛，因为 \(y_e\) 可大于 0 且 \(x_u+x_v=1\)，满足。我们还有上界互补松弛：因为 \(x_v <1\)，所以 \(z_v=0\)。于是得到：
\[y_{12}+y_{13} = 3 \]
\[ y_{12}+y_{23} = 2 \]
\[ y_{13}+y_{23} = 2 \]
解这个线性方程组：由第一式减第二式：\(y_{13}-y_{23}=1\)；结合第三式 \(y_{13}+y_{23}=2\)，得 \(2y_{13}=3 \Rightarrow y_{13}=1.5\)，则 \(y_{23}=0.5\)，再代入第二式得 \(y_{12}=1.5\)。
检查：\(y_{12}=1.5, y_{13}=1.5, y_{23}=0.5\)，且 \(z_1=z_2=z_3=0\)。验证对偶约束：
顶点1：1.5+1.5=3 ≤ 3，成立（等号）；
顶点2：1.5+0.5=2 ≤ 2，成立；
顶点3：1.5+0.5=2 ≤ 2，成立。
对偶目标值：\(y_{12}+y_{13}+y_{23} = 1.5+1.5+0.5 = 3.5\)，等于原问题最优值。因此对偶解是可行的，并且验证了强对偶。
5. 对偶问题的组合解释
对偶问题（D）实际上与图的最大权匹配问题有关。如果我们忽略 \(z_v\)（即令 \(z_v=0\)），则约束变为 \(\sum_{e: v \in e} y_e \le w_v\)，这正好是图的最大权分数边填充（fractional edge packing）问题：为每条边分配一个非负值 \(y_e\)，使得每个顶点 \(v\) 关联的边值之和不超过其权重 \(w_v\)，最大化 \(\sum y_e\)。在顶点权重均为 1 时，这就是分数匹配（fractional matching）问题。加上 \(z_v\) 允许“超出”权重，但超出部分会在目标中减去。可以证明，在最优解中，\(z_v\) 恰好是超出部分，因此对偶问题等价于寻找一个边填充 \(y\)，最大化 \(\sum y_e - \sum_v \max(0, \sum_{e: v\in e} y_e - w_v)\)。
6. 利用对偶求原问题分数解
一般地，我们可以直接求解对偶线性规划（变量数为 \(|E|+|V|\)），得到最优对偶解 \((y^*, z^*)\)，然后利用互补松弛条件求原问题分数解 \(x^*\)：
- 如果对偶约束对顶点 \(v\) 是严格的（即 \(\sum_{e: v\in e} y_e^* - z_v^* < w_v\)），则 \(x_v^* = 0\)。
- 如果对偶约束是等号且 \(z_v^* > 0\)，则 \(x_v^* = 1\)（由上界互补松弛）。
- 如果对偶约束是等号且 \(z_v^* = 0\)，则 \(x_v^*\) 可由边约束的互补松驰和等式 \(\sum_{e: v\in e} y_e^* = w_v\) 联立求解（通常需要解一个线性系统，但往往有简单结构，如在二分图上可直接得到整数解）。
7. 总结
通过这个例子，我们看到了最小权顶点覆盖问题的线性规划松弛及其对偶形式，并利用一个小图验证了强对偶性。对偶问题提供了另一个视角：它试图将权重分配给边，但受到顶点权重限制。这种方法不仅是理论分析的基础（如设计 2-近似算法），也可用于实际求解分数松弛，再通过舍入得到整数解。