基于线性规划的图最小顶点覆盖问题的半定规划松弛与随机舍入算法求解示例
题目描述
考虑一个无向图 \(G = (V, E)\)，其中 \(V = \{1, 2, ..., n\}\) 是顶点集合，\(E\) 是边集合。一个顶点覆盖（Vertex Cover）是一个顶点子集 \(S \subseteq V\)，使得图中的每条边至少有一个端点属于 \(S\)。最小顶点覆盖问题（Minimum Vertex Cover Problem）的目标是找到一个顶点覆盖 \(S\)，使得其大小 \(|S|\) 最小。这是一个经典的 NP-Hard 组合优化问题。
本题目要求：使用半定规划（Semidefinite Programming, SDP）松弛和随机舍入（Randomized Rounding）技术，为最小顶点覆盖问题设计一个近似算法，并展示其求解过程。
解题过程
我们将循序渐进地完成以下步骤：
- 整数规划建模
- 半定规划松弛
- 求解半定规划松弛
- 随机舍入设计
- 近似比分析
- 实例演示
步骤 1：整数规划建模
为每个顶点 \(i \in V\) 引入一个变量 \(x_i \in \{0, 1\}\)，其中：
\[x_i = \begin{cases} 1, & \text{如果顶点 } i \text{ 被选入顶点覆盖} \\ 0, & \text{否则} \end{cases} \]
最小顶点覆盖问题可以表述为以下整数规划（IP）：
\[\begin{aligned} \min \quad & \sum_{i \in V} x_i \\ \text{s.t.} \quad & x_i + x_j \ge 1, \quad \forall (i,j) \in E \\ & x_i \in \{0, 1\}, \quad \forall i \in V \end{aligned} \]
约束条件 \(x_i + x_j \ge 1\) 确保每条边至少有一个端点被覆盖。
步骤 2：半定规划松弛
标准的线性规划松弛是放宽 \(x_i\) 为连续变量 \(0 \le x_i \le 1\)，但这里我们使用更强大的半定规划松弛。首先，引入向量变量 \(\mathbf{v}_i \in \mathbb{R}^{n+1}\)（也可以使用 \(\mathbb{R}^n\)，但常见的一种松弛是增加一个额外维度）。
定义向量 \(\mathbf{v}_0\) 作为一个固定的单位向量（例如 \(\mathbf{v}_0 = (1, 0, ..., 0)^\top\)），并为每个顶点 \(i\) 定义一个向量 \(\mathbf{v}_i\)，满足 \(\|\mathbf{v}_i\|_2 = 1\)。我们要求：
- 如果 \(x_i = 1\)，则 \(\mathbf{v}_i = -\mathbf{v}_0\)。
- 如果 \(x_i = 0\)，则 \(\mathbf{v}_i = \mathbf{v}_0\)。
这可以统一表达为：\(\mathbf{v}_i \cdot \mathbf{v}_0 = 1 - 2x_i\)。因为当 \(x_i = 0\) 时，点积为 1；当 \(x_i = 1\) 时，点积为 -1。
为了构造半定规划，我们引入一个半正定矩阵 \(Y \in \mathbb{R}^{(n+1)\times (n+1)}\)，其元素 \(Y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)，其中索引 \(0, 1, ..., n\) 对应向量 \(\mathbf{v}_0, \mathbf{v}_1, ..., \mathbf{v}_n\)。于是：
- 对角线元素：\(Y_{ii} = \|\mathbf{v}_i\|^2 = 1\)。
- \(Y_{0i} = \mathbf{v}_0 \cdot \mathbf{v}_i = 1 - 2x_i\)。
那么原目标函数 \(\sum_i x_i\) 可以用 \(Y_{0i}\) 表示：\(x_i = \frac{1 - Y_{0i}}{2}\)。
对于每条边 \((i,j) \in E\)，覆盖约束 \(x_i + x_j \ge 1\) 等价于：
\[\frac{1 - Y_{0i}}{2} + \frac{1 - Y_{0j}}{2} \ge 1 \quad \Rightarrow \quad Y_{0i} + Y_{0j} \le 0. \]
另外，我们可以添加三角形不等式约束以加强松弛（来自向量点积的性质）：对于任意三个向量 \(\mathbf{v}_i, \mathbf{v}_j, \mathbf{v}_k\)，有 \(\mathbf{v}_i \cdot \mathbf{v}_j + \mathbf{v}_j \cdot \mathbf{v}_k + \mathbf{v}_k \cdot \mathbf{v}_i \ge -1\)。这等价于：
\[Y_{ij} + Y_{jk} + Y_{ki} \ge -1. \]
但为简化，许多近似算法仅使用部分约束。
我们采用一个常用的 SDP 松弛模型：
\[\begin{aligned} \min \quad & \frac{1}{2} \sum_{i \in V} (1 - Y_{0i}) \\ \text{s.t.} \quad & Y_{0i} + Y_{0j} \le 0, \quad \forall (i,j) \in E \\ & Y_{ii} = 1, \quad \forall i = 0,1,...,n \\ & Y \succeq 0 \quad \text{（半正定约束）} \end{aligned} \]
这里目标函数即为 \(\sum_i x_i = \sum_i \frac{1 - Y_{0i}}{2}\)。
步骤 3：求解半定规划松弛
这是一个标准的半定规划问题，可以使用内点法（如 SeDuMi、SDPT3 等求解器）在多项式时间内求解。设最优解矩阵为 \(Y^*\)，其秩可能大于 1。我们需要从 \(Y^*\) 中恢复出一组单位向量 \(\{\mathbf{v}_i\}\)。
通过 Cholesky 分解或特征分解，我们可以得到向量表示 \(\mathbf{v}_0, \mathbf{v}_1, ..., \mathbf{v}_n \in \mathbb{R}^d\)（其中 \(d \le n+1\)），使得 \(Y_{ij}^* = \mathbf{v}_i \cdot \mathbf{v}_j\)，且 \(\|\mathbf{v}_i\| = 1\)。
步骤 4：随机舍入设计
已知向量 \(\mathbf{v}_0, \mathbf{v}_1, ..., \mathbf{v}_n\) 满足：
- \(\|\mathbf{v}_i\| = 1\)。
- 对于边 \((i,j) \in E\)，有 \(\mathbf{v}_0 \cdot \mathbf{v}_i + \mathbf{v}_0 \cdot \mathbf{v}_j \le 0\)。
现在设计随机舍入方案。一种经典方法是：
- 随机选取一个单位向量 \(\mathbf{r}\) 均匀分布在 \(d\) 维单位球面上。
- 对于每个顶点 \(i\)，如果 \(\mathbf{v}_i \cdot \mathbf{r} \ge \mathbf{v}_0 \cdot \mathbf{r}\)，则将顶点 \(i\) 加入覆盖集合 \(S\)。
等价地，定义阈值函数：\(\text{sign}(\mathbf{v}_i \cdot \mathbf{r} - \mathbf{v}_0 \cdot \mathbf{r})\)，但更简单的是比较点积大小。
另一种常见且分析更简单的舍入规则（基于 Goemans-Williamson 思想的变体）：
- 令 \(\theta_i\) 为向量 \(\mathbf{v}_i\) 与 \(\mathbf{v}_0\) 之间的夹角，即 \(\cos \theta_i = \mathbf{v}_0 \cdot \mathbf{v}_i\)。
- 顶点 \(i\) 被选入覆盖的概率设为 \(p_i = \frac{\theta_i}{\pi}\)。
由于 \(\mathbf{v}_0 \cdot \mathbf{v}_i = 1 - 2x_i^{\text{SDP}}\)，其中 \(x_i^{\text{SDP}}\) 是 SDP 松弛得到的分数解，我们可以直接基于 \(\theta_i\) 计算概率。
具体步骤：
- 从 \(Y^*\) 得到向量 \(\mathbf{v}_i\)。
- 计算 \(\theta_i = \arccos(\mathbf{v}_0 \cdot \mathbf{v}_i) \in [0, \pi]\)。
- 以概率 \(p_i = \min\left(1, \frac{\theta_i}{\pi}\right)\) 将顶点 \(i\) 加入覆盖 \(S\)。
步骤 5：近似比分析
我们简要分析该算法的期望近似比。
设 SDP 松弛的最优目标值为 \(\text{OPT}_{\text{SDP}} = \sum_i \frac{1 - \mathbf{v}_0 \cdot \mathbf{v}_i}{2}\)。
对于每条边 \((i,j) \in E\)，约束 \(\mathbf{v}_0 \cdot \mathbf{v}_i + \mathbf{v}_0 \cdot \mathbf{v}_j \le 0\) 意味着 \(\theta_i + \theta_j \ge \pi\)（因为 \(\cos\theta_i + \cos\theta_j \le 0\)）。可以证明，在概率 \(p_i = \theta_i / \pi\) 下，边 \((i,j)\) 被覆盖的概率为：
\[\mathbb{P}[\text{边 } (i,j) \text{ 被覆盖}] = p_i + p_j - p_i p_j \ge \frac{\theta_i + \theta_j}{\pi} - \frac{\theta_i \theta_j}{\pi^2}. \]
当 \(\theta_i + \theta_j \ge \pi\) 时，可以证明该概率至少为 \(1 - \frac{\theta_i \theta_j}{\pi^2}\)，且经过分析（可能需要更细致的推导），期望覆盖大小 \(\mathbb{E}[|S|] = \sum_i p_i = \sum_i \frac{\theta_i}{\pi}\)。
由于 \(x_i^{\text{SDP}} = \frac{1 - \cos\theta_i}{2}\)，且对于 \(\theta \in [0, \pi]\)，有不等式 \(\frac{\theta}{\pi} \le \alpha \cdot \frac{1 - \cos\theta}{2}\)，其中 \(\alpha \approx 2\)（更精确地，最大比值约 1.999...）。因此：
\[\mathbb{E}[|S|] \le \alpha \cdot \text{OPT}_{\text{SDP}} \le \alpha \cdot \text{OPT}, \]
其中 \(\text{OPT}\) 是整数规划的最优值。所以该算法是一个期望近似比为 \(\alpha\)（约 2）的随机近似算法。
步骤 6：实例演示
考虑一个简单图：\(V = \{1,2,3\}\)，边集 \(E = \{(1,2), (2,3), (1,3)\}\)（三角形图）。
SDP 松弛求解（手算示意）：
- 由于对称性，可设 \(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\) 与 \(\mathbf{v}_0\) 的夹角均为 \(\theta\)，且彼此之间的夹角相同。
- 覆盖约束：对每条边 \((i,j)\)，\(\cos\theta + \cos\theta \le 0 \Rightarrow 2\cos\theta \le 0 \Rightarrow \theta \ge \pi/2\)。
- 目标最小化 \(\sum_i \frac{1 - \cos\theta}{2} = \frac{3}{2}(1 - \cos\theta)\)。
- 在约束 \(\theta \ge \pi/2\) 下，取 \(\theta = \pi/2\) 最小化目标，此时 \(\cos\theta = 0\)，目标值 \(= \frac{3}{2}\)。
所以 SDP 最优值 \(= 1.5\)，实际最小顶点覆盖大小为 2（取任意两个顶点）。
随机舍入：
- \(\theta_i = \pi/2\)，概率 \(p_i = (\pi/2)/\pi = 0.5\)。
- 每个顶点以 0.5 概率独立地被选入覆盖。
- 期望覆盖大小 \(= 3 \times 0.5 = 1.5\)。
- 但可能产生无效覆盖（如只选了一个顶点），我们可以重复舍入直到得到一个覆盖（或采用条件期望去随机化），但期望大小仍为 1.5，而最优整数解为 2，近似比 1.5/2 = 0.75 < 2（注意这是因为此实例中 SDP 松弛值低于整数最优值，而舍入后期望值可能小于整数最优值，但保证覆盖所有边）。
实际上，对于此三角形图，任何含两个顶点的覆盖都是最优解，算法可能以一定概率得到大小 2 或 3 的覆盖，但期望大小为 1.5 并不意味着总能得到可行覆盖，因此在实际算法中，我们通常需要检查舍入结果是否为顶点覆盖，若不是则可通过简单贪心补全（将未覆盖边的端点加入），这会在期望近似比上增加一个小常数因子，仍保持在 2 以内。
通过上述步骤，我们完成了基于半定规划松弛与随机舍入的图最小顶点覆盖问题的近似算法设计与分析。