基于线性规划的图最小反馈边集问题的原始-对偶近似算法求解示例
问题描述
在图论中，给定一个有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是有向边集。一个反馈边集（Feedback Edge Set, FES）是指一个边子集 \(F \subseteq E\)，若从原图中移除 \(F\) 中的所有边，则剩余图中不再包含任何有向环。最小反馈边集问题要求找到一个边数最少的反馈边集。该问题是NP难的，但可通过线性规划（LP）松弛结合原始-对偶方法设计近似算法，最终得到一个2-近似解（即解的大小不超过最优解的两倍）。
解题过程
步骤1：建立整数规划模型
为每条边 \(e \in E\) 引入二进制变量 \(x_e\)：
- \(x_e = 1\) 表示边 \(e\) 被选入反馈边集 \(F\)；
- \(x_e = 0\) 表示未被选中。
目标是最小化反馈边集的大小：
\[\min \sum_{e \in E} x_e \]
约束条件要求：对于每一个有向环 \(C \subseteq E\)，至少有一条边被选中（即至少一条边被移除以破坏该环）：
\[\sum_{e \in C} x_e \geq 1 \quad \forall \text{有向环 } C \]
由于图中环的数量可能是指数级的，直接求解不可行，需采用原始-对偶方法避免显式列出所有约束。
步骤2：构造线性规划松弛及其对偶
将整数规划松弛为线性规划（允许 \(0 \leq x_e \leq 1\)）：
\[\text{(原始问题P)} \quad \min \sum_{e \in E} x_e \quad \text{s.t.} \quad \sum_{e \in C} x_e \geq 1 \ \forall C, \ x_e \geq 0 \]
为每个环 \(C\) 引入对偶变量 \(y_C \geq 0\)，得到对偶问题：
\[\text{(对偶问题D)} \quad \max \sum_{C} y_C \quad \text{s.t.} \quad \sum_{C \ni e} y_C \leq 1 \ \forall e \in E, \ y_C \geq 0 \]
对偶约束的含义：每条边 \(e\) 被所有包含它的环的对偶变量和“覆盖”，且总和不超过1。
步骤3：原始-对偶近似算法设计
算法通过逐步构造对偶解 \(y\) 和整数原始解 \(x\)（即反馈边集 \(F\)）来实现：
- 初始化：令 \(y_C = 0\) 对所有环 \(C\)，\(F = \emptyset\)。
- 循环增加对偶变量：
- 当图中存在有向环时，任选一个环 \(C\)（例如通过深度优先搜索找到）。
- 将该环 \(C\) 对应的对偶变量 \(y_C\) 增加 \(\delta\)，直到某条边 \(e \in C\) 的对偶约束“紧”（即 \(\sum_{C' \ni e} y_{C'} = 1\)）。
- 将所有这样的紧边加入 \(F\)，并从图中移除它们（因为移除了这些边会破坏环 \(C\)）。
- 终止：当图中无环时停止，输出 \(F\) 作为反馈边集。
步骤4：算法正确性与近似比分析
- 可行性：算法结束时图中无环，故 \(F\) 是反馈边集。
- 近似比：设最优解为 \(F^*\)，算法解为 \(F\)。
由对偶可行性：
\[ \sum_{e \in F} \sum_{C \ni e} y_C = \sum_{C} |F \cap C| y_C \]
由于每次加入 \(F\) 的边至少属于当前环 \(C\) 且满足 \(|F \cap C| \geq 1\)，有：
\[ \sum_{C} |F \cap C| y_C \geq \sum_{C} y_C \]
结合原始目标值 \(|F| = \sum_{e \in F} 1 \geq \sum_{e \in F} \sum_{C \ni e} y_C\)（因紧边满足 \(\sum_{C \ni e} y_C = 1\)），得：
\[ |F| \geq \sum_{C} y_C \]
而对偶目标值 \(\sum_{C} y_C\) 是原始最优解的下界（弱对偶定理），故 \(|F| \leq 2 \sum_{C} y_C \leq 2 |F^*|\)，即算法为2-近似。
步骤5：示例演示
考虑有向图 \(G\) 包含环 \(C_1: a \to b \to c \to a\) 和 \(C_2: b \to d \to c \to b\)。
- 初始化 \(y_{C_1} = y_{C_2} = 0\)，\(F = \emptyset\)。
- 选择环 \(C_1\)，增加 \(y_{C_1}\) 至1，边 \((a,b), (b,c), (c,a)\) 均变紧，任选一条（如 \((a,b)\)）加入 \(F\)。移除 \((a,b)\) 后，环 \(C_1\) 被破坏。
- 剩余图中环 \(C_2\) 仍存在，增加 \(y_{C_2}\) 至1，边 \((b,d), (d,c), (c,b)\) 变紧，任选一条（如 \((b,d)\)）加入 \(F\)。
- 图中无环，输出 \(F = \{(a,b), (b,d)\}\)。
最优解可能是 \(\{(c,a), (c,b)\}\)（大小为2），算法解大小也为2，满足近似比要求。
总结
通过线性规划对偶理论结合组合搜索，原始-对偶方法避免了直接处理指数级约束，以多项式时间得到最小反馈边集的2-近似解。此方法可扩展至其他覆盖类问题。