基于线性规划的图最小反馈顶点集问题的半定规划松弛与随机舍入算法求解示例
我将为您讲解一个结合了线性规划、半定规划和随机舍入算法的图论优化问题。这个题目涉及如何将一个离散的组合优化问题松弛为连续的凸优化问题，并设计近似算法。
1. 问题描述
问题：给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集（\(|V| = n\)），\(E\) 是边集。一个反馈顶点集（Feedback Vertex Set, FVS）是一个顶点子集 \(S \subseteq V\)，使得移除 \(S\) 中的所有顶点后，剩余子图 \(G[V \setminus S]\) 中不包含任何环（即成为森林）。最小反馈顶点集（Min-FVS）问题是寻找一个顶点数最少的反馈顶点集。
这是一个经典的 NP-难问题。我们将通过以下步骤求解：
- 建立整数线性规划（ILP）模型。
- 将其松弛为半定规划（SDP）问题。
- 使用随机舍入技术，从 SDP 解构造整数可行解，并分析其近似比。
2. 解题过程
步骤 1：建立整数线性规划模型
我们引入二元变量 \(x_v\) 表示顶点 \(v\) 是否被选入反馈顶点集 \(S\)：
\[x_v = \begin{cases} 1, & \text{如果 } v \in S \\ 0, & \text{否则} \end{cases} \]
目标是最小化所选顶点数：
\[\text{最小化} \sum_{v \in V} x_v \]
关键约束：对于图中的每个环 \(C\)，至少有一个顶点在 \(S\) 中。但环的数量是指数级的，无法显式列出。我们使用另一种刻画：图无环当且仅当其每个连通分量是树，等价于边数不超过顶点数减 1。因此，对于任意顶点子集 \(U \subseteq V\)，诱导子图 \(G[U]\) 的边数必须满足：
\[|E(U)| \leq |U| - 1, \quad \text{如果 } U \text{ 是 } G[V \setminus S] \text{ 的顶点集} \]
用变量表示：剩余顶点集为 \(\{ v \mid x_v = 0 \}\)。定义 \(y_v = 1 - x_v\) 表示顶点 \(v\) 是否保留在无环子图中。则对任意 \(U \subseteq V\)，有：
\[\sum_{\{u,v\} \in E(U)} y_u y_v \leq \sum_{v \in U} y_v - 1 \]
由于 \(y_u y_v\) 是非线性项，直接处理困难。我们将其线性化：对于每条边 \(e = \{u, v\} \in E\)，引入变量 \(z_e\) 表示该边是否保留在无环子图中。约束为：
- 如果一条边被保留，则它的两个端点必须被保留：\(z_e \leq y_u\) 且 \(z_e \leq y_v\)。
- 对任意 \(U \subseteq V\)，保留在 \(U\) 中的边数不超过 \(U\) 中保留的顶点数减 1：\(\sum_{e \in E(U)} z_e \leq \sum_{v \in U} y_v - 1\)。
但子集 \(U\) 仍为指数多个。我们将问题放松，考虑所有顶点集 \(U\) 的约束，并加入目标中。
简化建模（常用松弛方法）：忽略子集约束，先考虑覆盖所有环的简单条件。利用图论事实：每个环至少 3 个顶点。对每个三角形（3-环）添加约束：三角形三个顶点对应的 \(x\) 变量之和至少为 1（即至少选一个顶点到 FVS 中）。虽然这不能覆盖所有环，但提供了有效下界。然后我们可对一般环通过半定规划加强。
ILP 公式（仅三角形约束）：
\[\begin{aligned} \min \quad & \sum_{v \in V} x_v \\ \text{s.t.} \quad & x_u + x_v + x_w \geq 1, \quad \forall \text{ 三角形 } (u, v, w) \in T \\ & x_v \in \{0,1\}, \quad \forall v \in V \end{aligned} \]
其中 \(T\) 是图中所有三角形的集合。此 ILP 是原问题的松弛（可行解集更大），其最优值 ≤ 实际 Min-FVS 的最优值。
步骤 2：半定规划松弛
我们构建更强的半定规划松弛，能编码更复杂的环约束。
步骤 2.1：向量表示
为每个顶点 \(v\) 分配一个单位向量 \(\mathbf{v} \in \mathbb{R}^{n+1}\)，并引入一个特殊单位向量 \(\mathbf{e}_0\) 表示“被选入 FVS”的状态。定义：
\[x_v = \frac{1 - \mathbf{v} \cdot \mathbf{e}_0}{2} \]
即，如果 \(\mathbf{v}\) 与 \(\mathbf{e}_0\) 同向（点积 1），则 \(x_v = 0\)（顶点保留）；如果反向（点积 -1），则 \(x_v = 1\)（顶点被移除）。于是 \(x_v \in [0,1]\) 连续。
步骤 2.2：三角形约束的向量形式
对三角形 \((u, v, w)\)，约束 \(x_u + x_v + x_w \geq 1\) 等价于：
\[(1 - \mathbf{u} \cdot \mathbf{e}_0) + (1 - \mathbf{v} \cdot \mathbf{e}_0) + (1 - \mathbf{w} \cdot \mathbf{e}_0) \geq 2 \]
化简得：
\[\mathbf{u} \cdot \mathbf{e}_0 + \mathbf{v} \cdot \mathbf{e}_0 + \mathbf{w} \cdot \mathbf{e}_0 \leq 1 \]
步骤 2.3：无环条件的半定约束
为加强松弛，对任意环添加约束。利用向量点积的性质：如果三个向量两两夹角较大，则它们的和与某个固定向量的点积受限。可添加对任意三条边形成的路径的约束，但通常采用以下简化全局约束：
对所有顶点对 \(u, v\)，要求 \(\mathbf{u} \cdot \mathbf{v} \geq -1 + 2\delta_{uv}\)，其中 \(\delta_{uv}\) 是辅助变量，但此方法较复杂。更实用的经典松弛是：
定义矩阵 \(Y = [y_{ij}]\) 其中 \(y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)。则 \(Y \succeq 0\)（半正定）。添加约束：对每条边 \((i,j) \in E\)，有 \(y_{ij} \leq y_{ii} = 1\)，且可加入三角形不等式：对任意三个顶点 \(i,j,k\)，
\[y_{ij} + y_{jk} + y_{ki} \geq -1 \]
这有助于捕捉环结构。
目标函数：最小化 \(\sum_{v} \frac{1 - \mathbf{v} \cdot \mathbf{e}_0}{2}\)。
完整 SDP 可为：
\[\begin{aligned} \min \quad & \frac{1}{2} \sum_{v \in V} (1 - \mathbf{v} \cdot \mathbf{e}_0) \\ \text{s.t.} \quad & \mathbf{u} \cdot \mathbf{e}_0 + \mathbf{v} \cdot \mathbf{e}_0 + \mathbf{w} \cdot \mathbf{e}_0 \leq 1, \quad \forall \text{ 三角形 } (u,v,w) \\ & \mathbf{v} \cdot \mathbf{v} = 1, \quad \forall v \in V \cup \{\mathbf{e}_0\} \\ & \mathbf{u} \cdot \mathbf{v} + \mathbf{v} \cdot \mathbf{w} + \mathbf{w} \cdot \mathbf{u} \geq -1, \quad \forall u,v,w \in V \\ & \mathbf{e}_0 \cdot \mathbf{e}_0 = 1, \\ & Y \succeq 0, \quad \text{其中 } Y_{uv} = \mathbf{u} \cdot \mathbf{v}. \end{aligned} \]
此 SDP 可在多项式时间内求解（使用内点法），得到最优解 \(\{\mathbf{v}^*\}\) 和最优值 \(\text{SDP-OPT} \leq \text{OPT}\)。
步骤 3：随机舍入算法
输入：图 \(G = (V, E)\)，SDP 最优解 \(\{\mathbf{v}^*\}\)。
算法：
- 随机选取一个单位向量 \(\mathbf{r} \in \mathbb{R}^{n+1}\)（从均匀分布的单位球面上）。
- 定义阈值集合：
\[ S = \left\{ v \in V \mid \mathbf{v}^* \cdot \mathbf{e}_0 < 0 \ \text{或} \ \mathbf{v}^* \cdot \mathbf{r} \geq \theta \right\}, \]
其中 \(\theta\) 是一个阈值参数，通常设为 0 或一个小正数。直观：如果向量 \(\mathbf{v}^*\) 与 \(\mathbf{e}_0\) 反向（即 \(x_v\) 大），则很可能被选入 FVS；同时，如果与随机方向 \(\mathbf{r}\) 夹角较小（点积大），也被选入，以打破可能剩余的环。
3. 输出 \(S\) 作为反馈顶点集。
解释：第一步条件（\(\mathbf{v}^* \cdot \mathbf{e}_0 < 0\)）对应 SDP 中 \(x_v > 1/2\) 的顶点，它们以高概率被选中。第二步条件（与随机方向比较）是一个常见技巧：在向量空间中，如果三个向量两两夹角较大（满足三角形不等式），则它们不太可能都在同一个半空间内（即同时有较大的点积与 \(\mathbf{r}\)），因此一个环上的顶点不太可能全部避开集合 \(S\)，从而能覆盖环。
步骤 4：分析与近似比
可证该算法是期望 \(O(\log n)\) 近似（在一般图上）。更精细的分析可得近似比 \(O(\log n)\)。证明思路：
- 首先，期望代价 \(E[|S|] = \sum_v \Pr[v \in S] \leq 2 \sum_v \frac{1 - \mathbf{v}^* \cdot \mathbf{e}_0}{2} = \text{SDP-OPT} \cdot O(1)\) 在某些参数设置下成立。
- 其次，证明对任意环 \(C\)，算法生成的 \(S\) 以高概率包含 \(C\) 中至少一个顶点。这是因为环上顶点的向量满足三角形不等式，使得它们不能全部与 \(\mathbf{r}\) 有较大的正点积，因此至少一个顶点进入 \(S\)。
- 最后，通过条件概率和并界论证，得到 \(S\) 是反馈顶点集的概率足够高，可通过重复执行取最小集合来保证确定性算法。
近似比：该算法能达到 \(O(\log n)\) 的近似比，这是目前多项式时间内最好的近似比之一（除非 P=NP）。
3. 总结
本问题展示了如何将 NP-难的图问题通过半定规划松弛，并利用随机舍入获得近似解。关键步骤包括：
- 用 ILP 建模，但约束难以处理。
- 用向量和半定规划捕捉组合结构，得到可多项式求解的松弛。
- 设计基于随机超平面的舍入策略，从连续解得到离散解。
- 分析舍入过程的近似保证。
此方法是组合优化中“线性/半定规划松弛 + 随机舍入”框架的经典应用，适用于顶点覆盖、最大割等问题，并能推广到其它反馈集问题。