顶点覆盖

2025 年 3 月 17 日 | 阅读 1 分钟

图 G 的顶点覆盖是一个顶点集合，使得 G 中的每条边都与这些顶点中的至少一个相关联。

证明了判定顶点覆盖问题是 NPC 的。现在，我们想要解决顶点覆盖问题的最优版本，即，我们想要找到给定图的最小大小顶点覆盖。我们将这样的顶点覆盖称为最优顶点覆盖 C*。

顶点覆盖的近似算法

Approx-Vertex-Cover (G = (V, E))
{           
       C = empty-set;
    E'= E;
    While E' is not empty do
      {
    Let (u, v) be any edge in E': (*)
    Add u and v to C;
    Remove from E' all edges incident to
       u or v;
      }
    Return C;
}

这个想法是逐个选取一条边 (u, v)，将两个顶点都放入 C 中，并删除与 u 或 v 相关联的所有边。我们继续这样做，直到所有边都被删除。 C 是一个 VC。但是 C 有多好？