基于线性规划的图最小反馈弧集问题的原始-对偶近似算法求解示例 问题描述 给定一个有向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个非负权重 \( w_ e \)。最小反馈弧集问题要求删除一个边集 \( F \subseteq E \)，使得图中不再有有向环（即剩余图是无环的），且删除边的总权重 \( \sum_ {e \in F} w_ e \) 最小。该问题可建模为整数规划，但因其NP难性质，需设计近似算法。下面通过原始-对偶方法，结合线性规划松弛和对偶理论，构造一个2-近似算法。 步骤1：建立整数规划模型 定义变量 \( x_ e \in \{0,1\} \) 表示边 \( e \) 是否被删除（1为删除）。目标是最小化总权重： \[ \min \sum_ {e \in E} w_ 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 \)。原始线性规划（LP）为： \[ \min \sum_ {e \in E} w_ e x_ e \quad \text{s.t.} \quad \sum_ {e \in C} x_ e \geq 1 \ (\forall C),\ x_ e \geq 0. \] 其对偶问题引入变量 \( y_ C \geq 0 \) 对应每个环 \( C \)： \[ \max \sum_ {C} y_ C \quad \text{s.t.} \quad \sum_ {C: e \in C} y_ C \leq w_ e \ (\forall e \in E),\ y_ C \geq 0. \] 对偶变量 \( y_ C \) 可解释为环 \( C \) 的“权重”。 步骤3：原始-对偶框架设计 算法逐步构造原始解 \( x \) 和对偶解 \( y \)： 初始化 ：设 \( x_ e = 0 \)（初始无删除边），\( y_ C = 0 \)（对偶未激活）。 迭代过程 ： 寻找当前图中最小权重的边集，使其覆盖所有未被满足的环（通过最大对偶约束调整）。 逐步增加对偶变量 \( y_ C \)（实际操作中通过边权减少模拟），直到某条边 \( e \) 的对偶约束紧（即 \( \sum_ {C: e \in C} y_ C = w_ e \)）。 将此类边加入删除集 \( F \)，并移除这些边以破坏环。 终止条件 ：当图中无环时停止。 步骤4：具体操作与近似比分析 边权减少 ：维护剩余边权 \( w_ e' = w_ e - \sum_ {C: e \in C} y_ C \)。当 \( w_ e' = 0 \) 时，边 \( e \) 的对偶约束紧，将其加入 \( F \) 并移除。 环检测 ：每次移除边后，检查剩余图是否无环（使用拓扑排序）。若存在环，继续增加该环的对偶变量 \( y_ C \)（同时减少环中边的剩余权重）。 近似比 ：算法最终输出的 \( F \) 是可行解（无环），且总权重满足： \[ \sum_ {e \in F} w_ e = \sum_ {e \in F} \sum_ {C: e \in C} y_ C \leq 2 \sum_ {C} y_ C \leq 2 \cdot \mathrm{OPT}. \] 其中第一个不等式是因为每条边最多被两个环共享（基于图结构分析），第二个不等式因对偶目标值不超过原始最优值 \( \mathrm{OPT} \)。 步骤5：示例演示 考虑有向图 \( V = \{1,2,3\} \)，边 \( E = \{(1,2), (2,3), (3,1)\} \)，权重均为1。 初始化：\( x_ e = 0 \)，边权全为1。 检测到环 \( C = \{(1,2),(2,3),(3,1)\} \)，增加 \( y_ C \) 至1，边权减为0，三条边均加入 \( F \)。 剩余图无边，终止。输出 \( F = E \)，权重和为3。 实际最优解是删除任意一条边（权重1），但算法在极端情况下达到2倍近似。 总结 通过原始-对偶方法，将指数级环约束转化为逐步权调整过程，得到一个高效且理论保证的2-近似算法。此方法避免了直接求解大规模LP，适用于实际中的大规模图优化问题。