最小顶点覆盖问题

最小顶点覆盖问题（minimum vertex cover problem）要求在无向图中选尽可能少的顶点，使每条边至少有一个端点被选中。它描述的是用顶点覆盖全部连接关系；例如把边视作必须检查的连接，选择端点上的检查位置就要触及每条连接。

覆盖一条边与覆盖全部边

设 $G=(V,E)$ 为有限简单无向图。若 $C\subseteq V$ 满足 $$\mathrm{\forall }\{u,v\}\in E,u\in C\text{或}v\in C,$$ 便称 $C$ 为顶点覆盖。其最小大小记为 $\tau (G)$。空边集的最优值为零，孤立顶点无须选择。这里覆盖的是边，不要求每个顶点都被选择或与被选顶点相邻。

五点路径 $0-1-2-3-4$ 的覆盖 $\{1,3\}$ 同时触及四条边：顶点 $1$ 覆盖前两条，顶点 $3$ 覆盖后两条。两条不相交的边 $01$ 与 $23$ 又要求覆盖至少各选一个不同端点，所以任何覆盖都至少有两个顶点，得出 $\tau (G)=2$。

上图选择顶点1和3即覆盖全部边。下图从匹配边01、23的全部端点构造覆盖，得到四点，仍然可行。

二元变量模型为 $$\begin{array}{cc}& min\sum _{v\in V}{x}_v,\\ & x_u+x_v\ge 1(\{u,v\}\in E),\\ & x_v\in \{0,1\}.\end{array}$$ 其中一条边不允许两个端点同时取零。与此对应，未被选择的顶点之间不应再有边，所以 $C$ 是覆盖当且仅当 $V\setminus C$ 是独立集，并有 $\tau (G)=|V|-\alpha (G)$。这也解释了两种精确优化问题的对应关系。

匹配给出的下界

匹配是两两没有公共端点的一组边。若一个匹配有 $k$ 条边，则每条边都要由覆盖触及；又因为这些边的端点互不重合，同一个顶点无法同时触及其中两条。因此 $$\tau (G)\ge k.$$ 这不是说最小覆盖总等于最大匹配。在三角形中，最大匹配只有一条边，而顶点覆盖至少需要两个顶点。对二分图，二者相等是另一个专门定理；上述一般下界的证明不依赖那个定理。

一个匹配是极大匹配，指再也不能加入新边而仍保持匹配，并不要求边数最多。从这种匹配的所有端点就能构造覆盖：倘若有一条边的两个端点都未被选，它与匹配中每条边都不接触，便可以加入匹配，违背极大性。

二倍近似及其证明

按一个固定顺序扫描各边，遇到两个端点都尚未匹配的边，就把它加入匹配。扫描完成后不可能再加入边：没有加入的边在当时至少有一个端点已经匹配，之后该端点仍然匹配。故所得匹配 $M$ 是极大的。

令 $C$ 为 $M$ 所有端点的集合。由上一节，$C$ 覆盖全部边；由匹配的端点不重合，$|C|=2|M|$；由下界，$|M|\le \tau (G)$。合并得到 $$\tau (G)\le |C|=2|M|\le 2\tau (G).$$ 这就是二倍近似保证。最优值为零时，算法也返回空集，不需要用零作分母来定义比例。

在五点路径上按 $01,12,23,34$ 扫描，选择匹配边 $01,23$，返回 $\{0,1,2,3\}$。它比最优覆盖多两个点，大小恰为最优值的两倍，说明这一算法的保证在某些实例上确实达到。换一种边顺序可能改善结果，但不会破坏上述界。

Python实现与核对

输入顶点编号为 $0,\dots ,n-1$ 的有限边序列；实现按该序列构造极大匹配，并返回端点元组和匹配边元组，不改写输入。重复边允许；自环或非法编号会报错。算法不是精确最优求解器。

Python 3

def approximate_vertex_cover(n, edges):
    if type(n) is not int or n < 0:
        raise ValueError("n must be a nonnegative integer")
    used = [False] * n
    matching = []
    for u, v in edges:
        if type(u) is not int or type(v) is not int:
            raise ValueError("vertex labels must be integers")
        if not (0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("require distinct vertices in range")
        if not used[u] and not used[v]:
            matching.append((u, v))
            used[u] = used[v] = True
    cover = tuple(v for v in range(n) if used[v])
    return cover, tuple(matching)

edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
cover, matching = approximate_vertex_cover(5, edges)
print(cover)     # (0, 1, 2, 3)
print(matching)  # ((0, 1), (2, 3))
assert all(u in cover or v in cover for u, v in edges)
assert approximate_vertex_cover(3, []) == ((), ())

时间为 $O(n+|E|)$，额外空间为 $O(n)$，其中保存匹配最多需要 $n/2$ 条边。正确性来自“被取出的边始终没有公共端点”及“扫描结束后匹配极大”两个性质。

变式取四点环 $01,12,23,30$。匹配 $\{01,23\}$ 的端点仍有四个，而 $\{0,2\}$ 已覆盖全部边；匹配下界二证明后者最优。若给顶点增加不同的成本，就变成加权覆盖，直接取匹配边的两个端点不再具有这里的成本二倍保证。一般图的精确最小覆盖是 NP 难优化问题；近似界应与返回方案是否可行一起报告。