最小顶点覆盖问题（Minimum Vertex Cover）的精确算法（基于分支定界与剪枝）

题目描述

给定一个无向图 \(G = (V, E)\)，最小顶点覆盖（Minimum Vertex Cover）是指一个顶点集合 \(S \subseteq V\)，使得图中的每一条边都至少有一个端点在 \(S\) 中，并且要求 \(S\) 的大小尽可能小。
这是一个经典的 NP 难问题，但我们可以在中小规模图中通过精确算法（如分支定界）找到最优解。本题要求你设计并实现一个基于分支定界法的精确算法，求得最小顶点覆盖的大小及其具体方案。

解题过程

1. 问题理解与基础性质

• 顶点覆盖：若选择某个顶点加入覆盖集，则所有与其相连的边都被覆盖。
• 重要性质：在任意一条边 \((u, v)\) 中，至少有一个端点必须在覆盖集中。
• 分支定界思想：通过递归地尝试选择或不选择某个顶点，构建搜索树，同时利用上下界剪枝以减少搜索空间。

2. 基本递归（朴素回溯）

我们可以从一条未覆盖的边 \((u, v)\) 出发，产生两个分支：

• 分支1：选择 \(u\) 加入覆盖集，然后递归处理剩余图。
• 分支2：选择 \(v\) 加入覆盖集，然后递归处理剩余图。

伪代码框架（无优化）：

function MVC(G, cover_set):
    if 所有边已被覆盖：
        更新最优解（如果当前覆盖集更小）
        return
    选择一条未覆盖边 (u, v)
    MVC(G 去掉 u 及关联边, cover_set ∪ {u})  # 选择 u
    MVC(G 去掉 v 及关联边, cover_set ∪ {v})  # 选择 v

问题：搜索树大小为 \(O(2^n)\)，需要优化。

3. 关键优化：上下界剪枝

• 上界（Upper Bound）：当前已知的最小覆盖大小（初始可设为 |V| 或通过启发式算法得到，如贪心近似算法）。
• 下界（Lower Bound）：当前部分解必须达到的最小顶点数。常用方法：
  1. 未覆盖边数下界：因为每条边至少需要一个顶点，未覆盖边数除以 2（向上取整）可作为下界。
  2. 松弛线性规划下界：通过线性规划松弛（每个变量在 [0,1]）得到的最小值，但计算较慢。
  3. 简单下界：若图中有度为 1 的顶点，则其邻居必须被选（因为选择该顶点不如选择邻居覆盖更多边）。

4. 剪枝策略实现

在递归过程中：

• 若 当前覆盖大小 + 下界 ≥ 当前最优解大小，则剪枝。
• 优先处理高难度顶点（如度数高的顶点），因为选择它们可能更快覆盖更多边。

改进的递归步骤：

1. 预处理：反复应用以下简化规则：
   • 如果存在孤立顶点（度数为 0），直接删除。
   • 如果存在度为 1 的顶点 \(v\)，则将其邻居 \(u\) 加入覆盖集（因为选 \(u\) 比选 \(v\) 更优），并删除 \(u\) 及其关联边。
2. 选择分支边：选择度数最大的顶点 \(w\) 作为分支点（或选择未覆盖边中度数和的较大的边）。
3. 递归分支：
   • 分支 A：选择 \(w\) 加入覆盖集，删除 \(w\) 及其关联边，递归。
   • 分支 B：不选 \(w\)，则所有 \(w\) 的邻居必须被选（否则边 \((w, neighbor)\) 无法覆盖），将邻居加入覆盖集，删除它们及其关联边，递归。

5. 算法流程示例

假设图有顶点 {1,2,3,4}，边：{(1,2), (2,3), (3,4), (4,1)}（一个 4 环）。

步骤：

1. 初始最优解上界 = 4（全选）。
2. 无度为 1 的顶点，直接进入分支。
3. 选择顶点 1（度数 2）分支：
   • 分支1：选 1，覆盖边 (1,2) 和 (1,4)。删除 1，剩余边 {(2,3), (3,4)}。
     • 选择顶点 2（度 1），邻居 3 必须选。
     • 选 3 后，覆盖 (2,3) 和 (3,4)，完成。覆盖集 {1,3}，大小 2。
     • 更新最优解 = 2。
   • 分支2：不选 1，则邻居 2 和 4 必须选（覆盖边 (1,2) 和 (1,4)）。删除 2 和 4，剩余边 {(3,?) 无}。覆盖集 {2,4}，大小 2。
     • 与当前最优解相同。
4. 最终最小顶点覆盖大小为 2，可能解为 {1,3} 或 {2,4}。

6. 时间复杂度与适用性

• 最坏情况仍为指数级，但剪枝能大幅减少搜索节点数。
• 适用于顶点数 \(n \leq 50\) 的中等规模图。
• 实际中常结合启发式初始解（如贪心得到的覆盖）提供紧上界。

7. 扩展思考

• 可以结合归约规则（如 Crown Reduction）在递归前简化图，进一步提升效率。
• 对于二分图，最小顶点覆盖大小等于最大匹配大小（König 定理），可用多项式算法解决。
• 分支定界法也适用于加权最小顶点覆盖问题（顶点有权重，求最小权重覆盖）。

总结：最小顶点覆盖的精确算法通过分支定界，结合上下界剪枝与图简化规则，能在合理时间内解决中小规模实例。