基于线性规划的图最小反馈边集问题的原始-对偶近似算法求解示例
问题描述
给定一个有向图 \(G = (V, E)\)，每条边 \(e \in E\) 有非负权重 \(w_e\)。目标是找到一个边集 \(F \subseteq E\)，使得移除 \(F\) 后图中无环（即剩余图是无环的），且 \(F\) 的总权重最小。此问题称为最小权重反馈边集问题（Minimum Weight Feedback Edge Set）。该问题是NP难的，但可通过原始-对偶框架设计近似算法。
解题过程
1. 问题建模为整数规划
定义变量 \(x_e \in \{0,1\}\)：若边 \(e\) 被选入反馈集 \(F\)，则 \(x_e = 1\)；否则为 0。目标是最小化总权重：
\[\min \sum_{e \in E} w_e x_e \]
约束条件：对图中每个有向环 \(C\)，至少有一条边被移除：
\[\sum_{e \in C} x_e \geq 1 \quad \forall \text{有向环 } C \]
由于环的数量是指数级的，直接求解不可行，需采用原始-对偶方法动态生成约束。
2. 构造线性规划松弛及对偶
将整数变量松弛为 \(x_e \geq 0\)，得到原始线性规划（P）：
\[\min \sum_{e} w_e x_e \quad \text{s.t.} \quad \sum_{e \in C} x_e \geq 1 \ \forall C, \ x_e \geq 0 \]
其对偶规划（D）为：
\[\max \sum_{C} y_C \quad \text{s.t.} \quad \sum_{C: e \in C} y_C \leq w_e \ \forall e, \ y_C \geq 0 \]
变量 \(y_C\) 对应每个环 \(C\)。
3. 原始-对偶近似算法框架
算法逐步构建反馈边集 \(F\) 和对偶变量 \(y\)：
- 初始化：\(F = \emptyset\)，所有 \(y_C = 0\)。
- 迭代过程：
（1）找到当前图中所有最小权重的边构成的子图，计算其强连通分量（SCC）。
（2）若整个图是无环的（SCC均为单点），终止；否则，选择一个SCC \(S\)（非单点），对其对应的环集合增加对偶值。
（3）设 \(\mathcal{C}_S\) 是所有完全包含在 \(S\) 内的环的集合。增加 \(y_C\)（对所有 \(C \in \mathcal{C}_S\)）直到某条边 \(e\) 的对偶约束紧（即 \(\sum_{C \ni e} y_C = w_e\)）。
（4）将所有紧边加入 \(F\)，移除后更新图。 - 输出：\(F\) 作为反馈边集。
4. 算法步骤详解
以示例有向图说明：
顶点集 \(V = \{1,2,3\}\)，边集 \(E = \{(1,2), (2,3), (3,1)\}\)，权重均为 1。
- 初始：图有一个环 \(C_0 = \{(1,2),(2,3),(3,1)\}\)，\(F = \emptyset\)。
- 迭代 1：
- 所有边权重相同，整个图是一个SCC \(S = \{1,2,3\}\)。
- 增加 \(y_{C_0}\) 从 0 到 1，使得边 (1,2)、(2,3)、(3,1) 的对偶约束均紧（因 \(\sum_{C \ni e} y_C = 1 = w_e\)）。
- 将所有紧边加入 \(F\)，此时 \(F = \{(1,2),(2,3),(3,1)\}\)。移除这些边后图无环，终止。
- 输出 \(F\) 的总权重为 3。
5. 近似比分析
算法输出的解满足：
\[\sum_{e \in F} w_e = \sum_{e \in F} \sum_{C \ni e} y_C = \sum_{C} y_C |F \cap C| \]
由于每个环 \(C\) 至少有一条边在 \(F\) 中（算法保证），有 \(|F \cap C| \geq 1\)。但对偶目标 \(\sum_C y_C\) 是最优解的下界，因此：
\[\text{算法解} \leq \sum_C y_C \cdot \max_C |F \cap C| \]
可证明 \(\max_C |F \cap C| \leq \nu\)（某常数），本例中 \(\nu = 2\)（通过更精细分析得近似比 2）。因此算法是 2-近似的。
6. 总结
通过原始-对偶方法，我们避免了枚举所有环，并在多项式时间内得到权重至多最优解 2 倍的反馈边集。关键点在于：
- 利用对偶变量引导边选择；
- 通过强连通分量识别环结构；
- 紧边对应权重的“耗尽”，保证可行性。