基于线性规划的图最小顶点覆盖问题的半正定规划松弛与随机舍入算法求解示例
我们将探讨如何将一个NP难的图最小顶点覆盖（Minimum Vertex Cover）问题，通过半正定规划（SDP）松弛和随机舍入技术，设计出一个近似算法。
1. 问题描述
- 输入：一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集，记 \(n = |V|, m = |E|\)。
- 目标：找到一个最小的顶点子集 \(S \subseteq V\)，使得对于图中的每一条边 \((u, v) \in E\)，至少有一个端点（\(u\) 或 \(v\)）在 \(S\) 中。这样的集合 \(S\) 称为一个顶点覆盖。
- 难点：该问题是经典的NP难问题，因此我们寻求高效的近似算法。
2. 整数规划建模
首先，我们为每个顶点 \(i \in V\) 引入一个二元决策变量 \(x_i\)：
- \(x_i = 1\) 表示顶点 \(i\) 被选入覆盖集 \(S\)。
- \(x_i = 0\) 表示顶点 \(i\) 未被选中。
那么最小顶点覆盖问题可以表述为以下整数规划（IP）：
\[\begin{aligned} \min \quad & \sum_{i \in V} x_i \\ \text{s.t.} \quad & x_i + x_j \geq 1, \quad \forall (i, j) \in E, \\ & x_i \in \{0, 1\}, \quad \forall i \in V. \end{aligned} \]
约束 \(x_i + x_j \geq 1\) 保证了每条边至少有一个端点被覆盖。
3. 线性规划松弛及其局限性
将整数约束松弛为线性约束，得到线性规划（LP）：
\[\begin{aligned} \min \quad & \sum_{i \in V} x_i \\ \text{s.t.} \quad & x_i + x_j \geq 1, \quad \forall (i, j) \in E, \\ & 0 \leq x_i \leq 1, \quad \forall i \in V. \end{aligned} \]
该LP可以在多项式时间内求解，最优解记为 \(x^*\)。通过简单的随机舍入（例如，以概率 \(x_i^*\) 将顶点 \(i\) 加入覆盖），可以证明得到一个期望大小为 \(2 \cdot \text{OPT}\) 的顶点覆盖，即这是一个2-近似算法。但是，这个近似比是紧的，在某些图上无法改进。
4. 半正定规划（SDP）松弛
为了获得更好的近似比（在某些情况下），我们可以采用更强大的SDP松弛。
步骤1：向量表示
为每个顶点 \(i\) 关联一个单位向量 \(\mathbf{v}_i \in \mathbb{R}^n\)，同时引入一个特殊向量 \(\mathbf{v}_0\)，用来区分“选中”和“未选中”状态。直观上：
- 如果 \(\mathbf{v}_i = \mathbf{v}_0\)，则顶点 \(i\) 被视为“未覆盖”（即 \(x_i = 0\)）。
- 如果 \(\mathbf{v}_i = -\mathbf{v}_0\)，则顶点 \(i\) 被视为“覆盖”（即 \(x_i = 1\)）。
因为向量是单位的，所以 \(\|\mathbf{v}_i\| = 1\)。
步骤2：将约束转化为向量形式
对于每条边 \((i, j)\)，覆盖约束要求两个顶点不能同时处于“未覆盖”状态。在向量模型中，“未覆盖”对应 \(\mathbf{v}_i = \mathbf{v}_0\) 且 \(\mathbf{v}_j = \mathbf{v}_0\)，此时它们的内积 \(\mathbf{v}_i \cdot \mathbf{v}_j = 1\)。我们希望禁止这种情况，因此要求：
\[\mathbf{v}_i \cdot \mathbf{v}_j \neq 1 \quad \text{或等价地} \quad \mathbf{v}_i \cdot \mathbf{v}_j \leq 1 - \delta \]
对于某个小的 \(\delta > 0\)。经过适当变换（详见后续），这可以转化为：
\[\mathbf{v}_i \cdot \mathbf{v}_j + \mathbf{v}_i \cdot \mathbf{v}_0 + \mathbf{v}_j \cdot \mathbf{v}_0 \leq -1. \]
这个形式可能看起来不直观，我们来推导一下。
步骤3：推导SDP约束
定义新的向量 \(\mathbf{u}_i\) 使得：
\[\mathbf{v}_i = \begin{pmatrix} \mathbf{u}_i \\ t_i \end{pmatrix}, \quad \mathbf{v}_0 = \begin{pmatrix} \mathbf{0} \\ 1 \end{pmatrix}, \]
其中 \(\mathbf{u}_i \in \mathbb{R}^{n}\)（或更高维），\(t_i \in \mathbb{R}\)，且要求 \(\|\mathbf{v}_i\|^2 = \|\mathbf{u}_i\|^2 + t_i^2 = 1\)。
设 \(x_i\) 表示顶点 \(i\) 被选中的概率。我们希望：
- 当 \(x_i = 0\)（未选中）时，\(\mathbf{v}_i = \mathbf{v}_0\)。
- 当 \(x_i = 1\)（选中）时，\(\mathbf{v}_i = -\mathbf{v}_0\)。
这可以统一表示为：\(\mathbf{v}_i = (1 - 2x_i) \mathbf{v}_0\)。那么内积为：
\[\mathbf{v}_i \cdot \mathbf{v}_j = (1 - 2x_i)(1 - 2x_j). \]
而 \(\mathbf{v}_i \cdot \mathbf{v}_0 = 1 - 2x_i\)。
现在，覆盖约束 \(x_i + x_j \geq 1\) 等价于 \((1 - 2x_i)(1 - 2x_j) \leq 0\)。因为：
- 如果 \(x_i + x_j \geq 1\)，那么 \(x_i\) 和 \(x_j\) 至少有一个为1。不妨设 \(x_i = 1\)，则 \(1 - 2x_i = -1\)，乘积 \((1 - 2x_i)(1 - 2x_j) \leq 0\)。
反之亦然。
所以，约束转化为：
\[\mathbf{v}_i \cdot \mathbf{v}_j \leq 0. \]
同时，\(\mathbf{v}_i \cdot \mathbf{v}_0 = 1 - 2x_i\)。
目标函数 \(\sum_i x_i\) 可以表示为：
\[x_i = \frac{1 - (\mathbf{v}_i \cdot \mathbf{v}_0)}{2}. \]
因此，最小化 \(\sum_i x_i\) 等价于最大化 \(\sum_i (\mathbf{v}_i \cdot \mathbf{v}_0)\)。
步骤4：SDP模型
令 \(\mathbf{v}_0, \mathbf{v}_1, \dots, \mathbf{v}_n\) 为单位向量。我们得到SDP：
\[\begin{aligned} \max \quad & \sum_{i=1}^n \mathbf{v}_i \cdot \mathbf{v}_0 \\ \text{s.t.} \quad & \mathbf{v}_i \cdot \mathbf{v}_j \leq 0, \quad \forall (i, j) \in E, \\ & \|\mathbf{v}_i\| = 1, \quad \forall i \in \{0, 1, \dots, n\}. \end{aligned} \]
这是一个半正定规划，因为向量内积可以表示为一个半正定矩阵 \(Y\)（其中 \(Y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)），且约束 \(\mathbf{v}_i \cdot \mathbf{v}_j \leq 0\) 是线性的。SDP可以在多项式时间内（近似）求解。
5. 随机舍入算法
求解上述SDP后，得到一组单位向量 \(\{\mathbf{v}_0, \mathbf{v}_1, \dots, \mathbf{v}_n\}\)。现在，我们需要将它们舍入成一个顶点覆盖。
一个经典方法是 随机超平面舍入：
- 随机选取一个单位向量 \(\mathbf{r}\)（均匀分布在单位球面上）。
- 对于每个顶点 \(i\)，计算 \(s_i = \operatorname{sign}(\mathbf{v}_i \cdot \mathbf{r})\)，即 \(\mathbf{v}_i\) 在随机方向 \(\mathbf{r}\) 上的投影的符号。
- 定义集合：
- \(S = \{ i \in V \mid s_i = s_0 \}\)，其中 \(s_0 = \operatorname{sign}(\mathbf{v}_0 \cdot \mathbf{r})\)。
即，将与 \(\mathbf{v}_0\) 落在超平面同一侧的顶点放入 \(S\)。
- \(S = \{ i \in V \mid s_i = s_0 \}\)，其中 \(s_0 = \operatorname{sign}(\mathbf{v}_0 \cdot \mathbf{r})\)。
- 输出 \(S\) 作为顶点覆盖。
6. 算法分析与近似比
我们需要证明：
- 可行性：输出的 \(S\) 确实是一个顶点覆盖。
- 近似比：期望大小 \(\mathbb{E}[|S|]\) 不超过某个倍数乘以SDP最优值（从而不超过最优整数解的某个倍数）。
可行性分析：
对于任意边 \((i, j) \in E\)，SDP约束要求 \(\mathbf{v}_i \cdot \mathbf{v}_j \leq 0\)。由于 \(\mathbf{v}_i\) 和 \(\mathbf{v}_j\) 之间的夹角至少为 \(90^\circ\)，随机超平面将它们分开的概率为1（实际上，它们不可能同时与 \(\mathbf{v}_0\) 落在同一侧的概率为1）。更严格地，通过几何概率可以证明，对于每条边，两个端点同时不在 \(S\) 中的概率为0，因此 \(S\) 必是顶点覆盖。
期望大小分析：
顶点 \(i\) 被加入 \(S\) 的概率是 \(\Pr[s_i = s_0]\)。根据随机超平面的性质，有：
\[\Pr[s_i = s_0] = 1 - \frac{\arccos(\mathbf{v}_i \cdot \mathbf{v}_0)}{\pi}. \]
利用不等式 \(1 - \frac{\theta}{\pi} \leq \frac{1}{2} + \frac{1}{2} \cos \theta\)（对 \(\theta \in [0, \pi]\)），我们有：
\[\Pr[s_i = s_0] \leq \frac{1}{2} + \frac{1}{2} (\mathbf{v}_i \cdot \mathbf{v}_0). \]
因此，
\[\mathbb{E}[|S|] = \sum_{i \in V} \Pr[s_i = s_0] \leq \frac{n}{2} + \frac{1}{2} \sum_{i \in V} (\mathbf{v}_i \cdot \mathbf{v}_0). \]
设SDP最优值为 \(\text{SDP}^* = \sum_i (\mathbf{v}_i \cdot \mathbf{v}_0)\)，则有：
\[\mathbb{E}[|S|] \leq \frac{n}{2} + \frac{1}{2} \text{SDP}^*. \]
由于整数最优解 \(\text{OPT} \geq \text{SDP}^*\)（SDP是松弛），并且 \(\text{OPT} \geq n/2\)（因为最大匹配的大小至少为 \(n/2\) 的下界，且顶点覆盖至少等于最大匹配大小），我们可以推导出 \(\mathbb{E}[|S|] \leq 2 \cdot \text{OPT}\)。实际上，对于某些图类（如二分图），该算法可以得到更接近的近似。
7. 总结
本示例展示了如何将最小顶点覆盖问题通过半正定规划松弛，并利用随机超平面舍入得到一个近似算法。虽然最坏情况近似比仍为2，但SDP松弛通常比LP松弛更紧，在实践中可能产生更好的解。此外，该方法展示了将组合优化问题提升到向量空间，利用几何概率进行分析的优美技巧。
通过这个循序渐进的过程，你应该能理解从问题建模到SDP松弛，再到随机舍入算法的完整思路。