基于线性规划的图最小顶点覆盖问题求解示例
问题描述
在图论中，给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。最小顶点覆盖问题要求找到一个顶点子集 \(S \subseteq V\)，使得每条边至少有一个端点属于 \(S\)，且 \(S\) 的规模最小。该问题是NP难问题，但可以通过线性规划松弛和舍入算法得到近似解。
解题步骤
- 整数规划建模
对每个顶点 \(v \in V\) 引入二进制变量 \(x_v \in \{0,1\}\)：
\[ x_v = \begin{cases} 1 & \text{顶点 } v \text{ 被选入覆盖集} \\ 0 & \text{否则} \end{cases} \]
目标函数是最小化覆盖集规模：
\[ \min \sum_{v \in V} x_v \]
约束条件要求每条边至少有一个端点被覆盖（对每条边 \((u,v) \in E\)）：
\[ x_u + x_v \geq 1 \]
- 线性规划松弛
将整数约束松弛为连续变量：
\[ 0 \leq x_v \leq 1 \quad \forall v \in V \]
得到线性规划问题：
\[ \min \sum_{v \in V} x_v \quad \text{s.t.} \quad x_u + x_v \geq 1 \ \forall (u,v) \in E \]
-
求解线性规划
使用单纯形法或内点法求解松弛问题，得到最优解 \(x^*\)。由于约束矩阵是全单模的（对于二部图），松弛解可能是整数解；但一般图中，解可能为分数。 -
舍入算法
采用确定性舍入策略：
\[ \hat{x}_v = \begin{cases} 1 & \text{若 } x_v^* \geq 0.5 \\ 0 & \text{否则} \end{cases} \]
验证舍入后的解是否满足约束：
- 对任意边 \((u,v)\)，若 \(x_u^* + x_v^* \geq 1\)，则 \(x_u^*\) 或 \(x_v^*\) 至少一个 \(\geq 0.5\)，舍入后该边被覆盖。
- 近似比分析
设 \(\text{OPT}\) 为整数规划最优值，\(\text{OPT}_{LP}\) 为线性规划最优值。由于松弛有 \(\text{OPT}_{LP} \leq \text{OPT}\)，且舍入后解满足：
\[ \sum_{v} \hat{x}_v \leq 2 \sum_{v} x_v^* = 2 \cdot \text{OPT}_{LP} \leq 2 \cdot \text{OPT} \]
因此算法是2-近似算法。
举例说明
考虑图 \(G\) 有顶点集 \(V = \{1,2,3\}\) 和边集 \(E = \{(1,2), (2,3), (1,3)\}\)（三角形图）：
- 整数规划约束：
\[ x_1 + x_2 \geq 1, \quad x_2 + x_3 \geq 1, \quad x_1 + x_3 \geq 1 \]
- 松弛后求解得 \(x_1^* = x_2^* = x_3^* = 0.5\)，目标函数值 \(1.5\)。
- 舍入后得 \(\hat{x}_1 = \hat{x}_2 = \hat{x}_3 = 1\)，覆盖集为 \(\{1,2,3\}\)，规模为 3。
实际最小顶点覆盖规模为 2（例如 \(\{1,2\}\)），验证了近似比界限。
总结
该方法通过线性规划松弛和简单舍入，以多项式时间得到最小顶点覆盖的2-近似解，展示了线性规划在组合优化中的强大应用。