基于线性规划的图最小边支配集问题的原始-对偶近似算法求解示例
题目描述
在图 \(G = (V, E)\) 中，一个边支配集（Edge Dominating Set）是边集 \(D \subseteq E\)，使得每条边 \(e \in E\) 要么属于 \(D\)，要么与 \(D\) 中的某条边相邻（即共享一个公共端点）。最小边支配集问题要求找到边数最少的边支配集。该问题是 NP-难问题，但可以通过线性规划松弛和原始-对偶方法设计近似算法。
解题过程
1. 整数规划建模
对每条边 \(e \in E\)，定义二进制变量 \(x_e \in \{0, 1\}\)：
\[x_e = \begin{cases} 1 & \text{若边 } e \text{ 被选入边支配集 } D, \\ 0 & \text{否则}. \end{cases} \]
目标是最小化边支配集的大小：
\[\min \sum_{e \in E} x_e. \]
约束条件：每条边必须被支配（即要么自身被选，要么至少有一条相邻边被选）。对任意边 \(e = (u, v) \in E\)，其相邻边集合为 \(\delta(e) = \{ f \in E \mid f \text{ 与 } e \text{ 有公共端点} \}\)。约束写为：
\[x_e + \sum_{f \in \delta(e)} x_f \geq 1 \quad \forall e \in E. \]
注意：若 \(e\) 被选（\(x_e = 1\)），约束自动满足；若 \(e\) 未被选，则至少一条相邻边必须被选。
2. 线性规划松弛
将整数约束松弛为线性约束：
\[\min \sum_{e \in E} x_e, \quad \text{s.t. } x_e + \sum_{f \in \delta(e)} x_f \geq 1 \ \forall e \in E, \quad x_e \geq 0 \ \forall e \in E. \]
由于约束矩阵是全单模的？实际上，边支配集问题的约束矩阵不是全单模的（例如，奇环的反例），因此松弛后的解可能是分数解。
3. 对偶问题
为每个约束引入对偶变量 \(y_e \geq 0\)（对应边 \(e\) 的约束）。对偶问题为：
\[\max \sum_{e \in E} y_e, \quad \text{s.t. } y_e + \sum_{f \in \delta(e)} y_f \leq 1 \ \forall e \in E, \quad y_e \geq 0 \ \forall e \in E. \]
对偶约束的含义：对每条边 \(e\)，其自身及其所有相邻边的对偶变量之和不超过 1。
4. 原始-对偶近似算法设计
算法分为两步：
- 对偶上升阶段：构造对偶可行解 \(y\)；
- 原始整数解构造阶段：利用对偶解生成边支配集 \(D\)。
步骤 4.1 对偶上升
初始化 \(y_e = 0\) 对所有边 \(e\)，\(D = \emptyset\)。
依次考虑每条边 \(e\)（按任意顺序），若 \(e\) 尚未被支配（即 \(e \notin D\) 且所有 \(f \in \delta(e)\) 均不在 \(D\) 中），则增加 \(y_e\) 直到某个约束变紧（即存在某条边 \(g\) 满足 \(y_g + \sum_{h \in \delta(g)} y_h = 1\)）。此时将 \(g\) 加入 \(D\)（即设置 \(x_g = 1\)），并标记所有与 \(g\) 相邻的边为已支配。
步骤 4.2 整数解构造
上述过程得到的 \(D\) 是边支配集，但可能包含冗余边（即某条边被加入后，其相邻边可能也被加入，导致冗余）。进行去冗余操作：按加入 \(D\) 的逆序检查每条边，若移除后剩余集合仍是边支配集，则移除它。
5. 近似比分析
设算法得到的边支配集大小为 \(|D|\)，对偶目标函数值为 \(\sum_{e} y_e\)。
- 对每条被选边 \(e \in D\)，其对偶约束在加入时变紧： \(y_e + \sum_{f \in \delta(e)} y_f = 1\)。
- 每条边至多被 \(e\) 及其相邻边共享，而每条边最多出现在两个约束中（因每条边有两个端点），但更精细的分析表明：每条对偶变量 \(y_f\) 至多出现在两个紧约束中（对应其两个端点的边）。
- 实际上，可证明 \(\sum_{e \in D} \left( y_e + \sum_{f \in \delta(e)} y_f \right) \leq 2 |D|\)（因为每条边最多被两个不同的选边相邻）。
- 由于每个紧约束值为 1，有 \(|D| \leq 2 \sum_{e} y_e\)。
- 由弱对偶定理，对偶目标值不超过最优原始解值 \(\mathrm{OPT}\)，故 \(|D| \leq 2 \cdot \mathrm{OPT}\)。
因此，算法是 2-近似算法。
总结
通过线性规划松弛、对偶问题构建和原始-对偶策略，我们得到了一个高效的最小边支配集 2-近似算法。该方法避免了直接求解整数规划，并保证了理论上的近似比。