基于线性规划的图最小反馈边集问题的对偶方法求解示例
问题描述
在图论中，反馈边集（Feedback Edge Set）是指删除后能使图变为无环（即破坏所有环）的边集合。最小反馈边集是包含边数最少的反馈边集。该问题可转化为线性规划模型，并通过对偶理论分析其性质。
输入：有向图 \(G = (V, E)\)，顶点集 \(V\) 大小为 \(n\)，边集 \(E\) 大小为 \(m\)。
目标：找到边数最少的最小反馈边集。
步骤1：建立线性规划模型
定义变量 \(x_e \in \{0, 1\}\) 表示边 \(e\) 是否被选入反馈边集（1表示选中）。但直接求解整数规划较难，先松弛为线性规划：
\[\min \sum_{e \in E} x_e \]
约束条件：对于图中的每一个有向环 \(C\)，至少有一条边被选中：
\[\sum_{e \in C} x_e \geq 1 \quad \text{（对每个环 $ C $）} \]
\[0 \leq x_e \leq 1 \quad \forall e \in E \]
由于环的数量可能指数级增长，直接列出所有约束不可行，但可通过对偶问题间接分析。
步骤2：构造对偶问题
原问题为最小化问题，约束为“≥”形式，变量非负。对偶变量 \(y_C \geq 0\) 对应每个环 \(C\)。
- 原问题目标函数系数为 \(1\)（每条边的成本）。
- 对偶约束：对每条边 \(e\)，其对应的对偶约束为
\[\sum_{C: e \in C} y_C \leq 1 \]
（因为原问题变量 \(x_e\) 在目标函数中的系数为1，在约束中系数为0或1）。
对偶问题为：
\[\max \sum_{C} y_C \]
\[\text{s.t.} \quad \sum_{C: e \in C} y_C \leq 1 \quad \forall e \in E \]
\[y_C \geq 0 \quad \forall \text{环 } C \]
对偶问题的意义：给每个环分配权重 \(y_C\)，使得每条边上的环权重总和不超过1，最大化环权重总和。
步骤3：对偶问题的组合解释
对偶问题实际上是最大环填充问题（Maximum Cycle Packing）：找到一组环（可重复），使每条边被使用的次数不超过1，最大化环的数量（或总权重）。
- 若环不重复（0-1权重），则是找边不交的环集合，最大化环数。
- 线性规划松弛允许环重复出现（权重可分数），但每条边上的总权重 ≤1。
关键性质（对偶定理）：
\[\text{原问题最优值} \geq \text{对偶问题最优值} \]
对于最小反馈边集，原问题最优值（最小边数）至少等于对偶问题最优值（最大环填充权重）。
步骤4：整数性 gap 与近似算法
虽然原问题是整数规划，但其线性规划松弛的整数性 gap 最大为2（对于有向图）。
- 利用对偶问题，可设计近似算法：
- 求解对偶问题的近似解（如贪心选择环）。
- 根据对偶解构造原问题的整数解（反馈边集）。
- 经典方法：
- 不断找到图中的环，删除环中一条边，直到无环。
- 利用对偶权重指导边删除（如优先删除权重低的边）。
步骤5：示例计算
考虑简单有向图：顶点集 \(V = \{1,2,3\}\)，边集 \(E = \{(1,2), (2,3), (3,1)\}\)（一个三角形环）。
- 环 \(C\) 包含所有三条边。
- 原问题约束：\(x_{12} + x_{23} + x_{31} \geq 1\)。
- 最优解：删除任意一条边（\(x_e=1\) 对于一条边，其他为0），成本=1。
- 对偶问题：变量 \(y_C\)，约束为每条边上的权重 ≤1。由于环包含所有边，约束为 \(y_C \leq 1\)（因为每条边只在一个环中）。
- 对偶最优解：\(y_C = 1\)，对偶目标值=1。
原问题与对偶最优值相等，说明线性规划松弛整数性 gap 为1（此例中整数解达到松弛下界）。
总结
通过将对偶理论应用于反馈边集问题，可将最小化问题转化为最大化环填充问题，从而揭示问题结构并设计近似算法。该方法适用于一般有向图，且可扩展至加权情形（边有权重时目标函数为加权和）。