在很多图问题里边代表一种关系依赖、冲突、通信、覆盖、监控、约束。Vertex Cover 问的是一个很直接的问题能不能选出尽量少的一批点使得每条边至少有一个端点被选中给定无向图 (,)G(V,E)若点集 ⊆C⊆V 满足对任意边 (,)∈(u,v)∈E都有 ∈u∈C 或 ∈v∈C那么 C 就是一个 vertex cover。要做到最优就要选出最少的点。无权版本的目标是最小化 ∣∣∣C∣。带权版本 Weighted Vertex Cover Problem 进一步给每个点 v 一个非负权重 wv目标变成最小化 ∑∈∑v∈Cwv。从最小化问题开始Vertex Cover 是一个最小化型组合优化问题。它是 NP-complete 问题。带权版本也完全一样。对于树、二分图、很小的参数 k、有特殊结构的图可以有更好的精确算法。真正困难的是一般图上的最优解输入只给你一个普通无向图不附带额外结构要求多项式时间内总是找出最小 vertex cover 是非常困难的。到这里通常就要接受一个现实精确最优很难近似解是这个问题的主战场。对最小化问题ρ 近似的意思是算法输出 A 满足 cost()≤⋅OPTcost(A)≤ρ⋅OPT。Vertex Cover 最经典的结论是 2ρ2。这不是一个随便冒出来的数字它来自一个非常简单的下界匹配。无权覆盖的 2 近似先抓一批互不相碰的边先看无权版本。一个常见算法是从图中找一条还没有被覆盖的边 (,)(u,v)把 u 和 v 都加入答案删除所有已经被 u 或 v 覆盖的边重复直到所有边都被覆盖。换一种说法这个算法实际上是在构造一个极大匹配。每次取到的边之间不会共享端点当算法停下时已经无法再加入新的边。最后把这些匹配边的两个端点全部选入 C。这里要区分“极大”和“最大”。极大匹配 maximal matching 只是说不能再往里面加边了最大匹配 maximum matching 才是边数真正最多的匹配。这个 2 近似算法求出的只是一个极大匹配因此实现非常轻。为什么它一定是一个覆盖上面的算法先求出一个图匹配再转化成对应的覆盖方案。设算法得到的匹配为 M输出 C 是 M 中所有边的端点集合。假设存在一条边 (,)(a,b) 没有被 C 覆盖也就是说 a 和 b 都没有出现在任何匹配边里。那么 (,)(a,b) 可以直接加入 M并且不会和原来的匹配边冲突。这和 M 已经极大矛盾。所以输出一定是一个 vertex cover。算法停机条件本身就是正确性的一部分。只要还有一条未覆盖边就继续抓如果停了说明不存在未覆盖边。为什么它最多差两倍接下来证明近似比。匹配 M 里的边两两不共享端点。任何 vertex cover 都必须覆盖 M 中的每条边而覆盖一条匹配边至少要选它的一个端点。由于这些边互不相交不可能用同一个点同时覆盖两条匹配边。因此任意最优解都至少要选 ∣∣∣M∣ 个点即 OPT≥∣∣OPT≥∣M∣。算法输出时每条匹配边选两个端点所以 ∣∣2∣∣∣C∣2∣M∣。于是有 ∣∣2∣∣≤2OPT∣C∣2∣M∣≤2OPT。这个证明很简单并且这个比率对该算法来说是紧的。我们可以构造一个星形图一个中心连出很多叶子。如果算法先拿到某条边 (,ℓ)(c,ℓ)它会把中心 c 和叶子 ℓℓ 都选进去。最优解只需要选中心 c所以这一次就已经是 22 对 11。当然输出仍然合法只是多选了一个叶子。带权覆盖情形Weighted Vertex Cover 的难点在于“拿一条边的两个端点”可能非常亏。假设只有一条边 (,)(u,v)1wu1106wv106。如果无脑选两个端点代价是 10000011000001最优解只选 u代价是 11。这显然不是 2 近似。带权版本常用的 2 近似解法巧妙的利用 LP 对偶和 primal-dual 。先写出整数规划的转换令 ∈0,1xv∈0,1 表示点 v 是否被选中每条边 (,)(u,v) 要求 ≥1xuxv≥1。放松 xv 的整数约束后得到线性规划min∑∈ s.t.≥1,∀(,)∈ ≥0,∀∈minv∈V∑wvxv s.t.xuxv≥1,∀(u,v)∈E xv≥0,∀v∈V它的对偶可以理解成给每条边设置一个“价格” yemax∑∈ s.t.∑∋≤,∀∈ ≥0,∀∈maxe∈E∑ye s.t.e∋v∑ye≤wv,∀v∈V ye≥0,∀e∈E对偶约束的意思是所有压到点 v 身上的边价格之和不能超过这个点的权重 wv。任何可行的对偶解都会给出一个下界因为任意 vertex cover 都要为每条边至少付一次账。定价法的直觉primal-dual 算法可以这样写C ∅所有边价格 y_e 0while 还有未被覆盖的边 e(u,v):同时提高 y_e直到 u 或 v 至少有一个点的预算被用满把预算用满的端点加入 C标记所有被 C 覆盖的边return C更具体地说每个点 v 有剩余预算 slack()−∑∋slack(v)wv−∑e∋vye。当处理未覆盖边 (,)(u,v) 时令 min(slack(),slack())δmin(slack(u),slack(v))把 (,)y(u,v) 增加 δ。此时至少一个端点变成 tight也就是预算刚好用满把这些 tight 的端点加入 C。如果某个点权重是 00它一开始就是 tight只要它能覆盖边选它没有坏处。权重为负通常不在标准定义里因为那会破坏“代价最小化”的正常含义。证明为什么还是 2算法始终保持对偶可行任何点的 incident edge 价格总和都不会超过它的权重。设最终边价格为 y。对任意最优 vertex cover ∗C∗由于 ∗C∗ 覆盖每条边所有边价格之和不会超过被 ∗C∗ 选中顶点的预算总和所以 ∑≤OPT∑eye≤OPT。另一方面算法选入 C 的每个点都是 tight 的因此∑∈∑∈∑∋v∈C∑wvv∈C∑e∋v∑ye右边是在数“被选中端点承担了多少边价格”。一条边最多有两个端点所以任何 ye 最多被数两次。因此 ∑∈≤2∑≤2OPT∑v∈Cwv≤2∑eye≤2OPT。这就是带权版本的 2 近似证明。它和无权匹配算法看起来不同本质上却很接近都在构造一个可证明的下界然后说明自己的解最多是这个下界的两倍。无权算法的下界是匹配大小带权算法的下界是对偶价格。它通向哪些经典问题Vertex Cover 不是孤立的。很多图论和组合优化问题都能从它旁边走出来。最直接的是 Independent Set。点集 C 是 vertex cover当且仅当 ∖V∖C 是 independent set。因为如果剩下的点里还有一条边那么这条边的两个端点都没被 C 选中C 就没有覆盖它。于是无权情形有 ()()∣∣τ(G)α(G)∣V∣其中 ()τ(G) 是最小 vertex cover 大小()α(G) 是最大 independent set 大小。再往前一步Independent Set 又和 Clique 互为补图问题图 G 中的 independent set对应补图 ‾G 中的 clique。所以 Vertex Cover、Independent Set、Clique 这三者在判定复杂度上几乎是同一枚硬币的不同面。给定是否存在大小不超过 k 的 vertex cover可以转成是否存在大小至少 ∣∣−∣V∣−k 的 independent set也可以转成补图中是否存在大小至少 ∣∣−∣V∣−k 的 clique。但这个互补关系不能随便拿来转移近似比。最小化 vertex cover 的一个 2 近似并不会自动给最大 independent set 一个好近似。原因是补集会把乘法误差变成很难控制的差值。比如 ∣∣−()∣V∣−τ(G) 很小的时候vertex cover 的一点点误差都可能把 independent set 的质量彻底冲掉。这也是近似算法里常见的坑精确解之间能互相转换不代表近似解之间也能保持比例。Vertex Cover 也可以看成 Set Cover 的一个特例。把边集 E 看成 universe每个顶点 v 对应一个集合 Sv里面包含所有 incident edges。选择一批顶点覆盖所有边就是选择一批集合覆盖整个 universe。特殊之处在于每条边恰好属于两个集合也就是它的两个端点。一般 Set Cover 的元素可能出现在很多集合里所以它的近似行为更差Vertex Cover 的“频率为 2”正是 2 近似能自然出现的原因。如果把普通边推广成超边就得到 Hypergraph Vertex Cover也常被看成 Hitting Set。每条超边可能包含多个顶点目标是选点打中每条超边。若每条超边大小最多为 f类似的 primal-dual 思路会给出 f 近似。普通 Vertex Cover 就是 2f2 的情况。Matching 则提供了另一个方向。一般图里最大匹配大小只是最小 vertex cover 的下界不一定相等。二分图里情况突然变好由 Kőnig 定理二分图的最小 vertex cover 大小等于最大匹配大小。因此二分图上的 Vertex Cover 可以多项式时间精确求解。带权二分图版本也能通过 LP 或最小割等方法解决。这是一个很好的边界问题本身没有变只是图类从一般图收缩到二分图困难性就消失了。有没有越过“两倍”的算法虽然 2 倍太宽了但是暂时没有很好的办法。在一般图上基于“唯一博弈猜想”UGC成立的理论前提下“2倍”被公认是一个无法越过的理论壁垒有的研究放宽了目标只追求“渐近”意义上的突破即对顶点数 n 极大的图能做到 2−Θ(1/log)2−Θ(1/logn) 倍虽然小于 2但差距会随 n 增大而无限缩小并非一个固定的常数。
